heeroyung

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?

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.

cwr

Here's another hint for you: Read This

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

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Up to 8Mb PlusNet broadband from only £5.99 a month!

Ancient Dragon

I haven't heard that one before.

heeroyung

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

heeroyung

do you mean using array?let me try first

Thantos

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

heeroyung

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

Rashakil Fol

Are you familiar with graphs?

Topological sort.

heeroyung

Topological sort
what's the meaning of this word?

Salem

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

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Up to 8Mb PlusNet broadband from only £5.99 a month!

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.

heeroyung

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. , 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.)

heeroyung

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