anyone know the solution?

Emily is a teacher. She likes to give candies to her students on days near festivals. She would like to give the candies to the students in order.

She decides to distribute the candies to them one by one, with a rule that if student A is teased by B, A can receive candy before B. But this is a troublesome and time consuming task as she is very busy.

You are asked to help Emily by writing a program to find the order of students that satisfies the rule.

Input

The first line of the input file contains an integer N (2 £ N £ 100), the number of students. The students are numbered as 1 to N. The following N lines describe each student being teased by whom. In the Kth line of those N lines, the first integer M (0 £ M < N) contains the number of students who tease student K, and the next M integers are the student numbers who tease student K.

Output

The output file should contain the sequence of student numbers separated by a space that Emily can distribute the candies with the rule satisfied. If there is more than one solution, you are only required to output anyone of them. If there is no solution, output "No Solution".

Sample Input 1


5
2 2 3
1 3
1 5
1 2
0

Sample Output 1

1 4 2 3 5



Sample Input 2

5
2 2 3
1 3
1 4
1 2
0

Sample Output 2

No Solution




do anyone know how to solve this problem?

I assume you can figure out input and output okay.

Here's a hint for you. This problem uses a datastructure that represents a graph.

Here's another hint for you: Read This

> do anyone know how to solve this problem?

This is a little story about four people named Everyone, Someone, Anyone, and Noone.

There was an important job to be done and Everyone was sure that Someone would do it.

Anyone could have done it, but Noone did it.

Someone got angry about that because it was Everyone's job.

Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

It ended up that Everyone blamed Someone when Noone did what Anyone could have done

Quote:

---

Originally Posted by Salem

> do anyone know how to solve this problem?

This is a little story about four people named Everyone, Someone, Anyone, and Noone.

There was an important job to be done and Everyone was sure that Someone would do it.

Anyone could have done it, but Noone did it.

Someone got angry about that because it was Everyone's job.

Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

It ended up that Everyone blamed Someone when Noone did what Anyone could have done

---

:D :D :D :D I haven't heard that one before. :D :D

Quote:

---

Originally Posted by cwr

Here's another hint for you: Read This

---

this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.

Quote:

---

Originally Posted by Rashakil Fol

I assume you can figure out input and output okay.

Here's a hint for you. This problem uses a datastructure that represents a graph.

---

do you mean using array?let me try first

Quote:

---

Originally Posted by heeroyung

this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.

---

Then actually study it. Asking if any of us know how to solve it doesn't help you at all.

Quote:

---

Originally Posted by Thantos

Then actually study it. Asking if any of us know how to solve it doesn't help you at all.

---

i have already think this problem for two days. i don't think it's wrong to ask for some hints.

Are you familiar with graphs?

Topological sort.

Topological sort
what's the meaning of this word?

> what's the meaning of this word?
Oh please tell me you've heard of google....

Quote:

---

Originally Posted by heeroyung

i have already think this problem for two days. i don't think it's wrong to ask for some hints.

---

Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.

Quote:

---

Originally Posted by Thantos

Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.

---

No need to say sorry. That's normal.

This question require us to find a correct order of students. This can be done by making an array, e.g.

Code:

---

student[5]={1,2,3,4,5}

---

, and then do swapping.if student 4 is teased by 1.the final array should be like that:{4,2,3,1,5}. The hardest problem is there may have some contradiction. e.g. student 4 is teased by 1 but student 1 is also teased by student 4! this come to another output--no solution. yesterday i thought one method---use array to store each student, and the following space store the number of students who tease this student. but i don't think this is a good method because the file size may be very large and the running time may be very long. so i hope to hear some opinions from you.

(if you still don't trust me, you can ask me to explain. since my english standard is very low, i hope you can understand what i am saying above.)

no one help me..................

Have you done any research on Rashakil Fol's suggestion?

Oh and don't bump you threads.