Hide

Problem A
Bíóferð

Languages en is
/problems/bioferd/file/statement/en/img-0001.jpg
Cinema by Deedee86, Pixabay
Sara likes going to the movies with her friends. When it comes to choosing seats it’s important that everyone is happy with the choice. The group chooses a single row and sits down somewhere in the row. Some people have strong preferences where to sit, but others do not.

For example, if the seats are numbered from right to left then Sara doesn’t want to sit in the first seat.

You get information about the preference of the group, who is going and where each person wants to seat. Can you help the group determine a satisfactory seating arrangement?

Input

The first line of the input contains an integer $1 \leq n \leq 10^3$, the size of the group. Then follow $n$ lines where each line starts with an integer $0 \leq k_ i \leq n$ and then follow $k_ i$ distinct integers $1 \leq x_{i,j} \leq n$ indicating the seats that person $i$ is satisfied with.

Output

Output a single line containing $n$ integers $a_1, a_2, \dots , a_ n$, where $a_ i$ indicates the number of the person in the $i$-th seat, from left to right. If there are multiple solutions, print any of them. If there is no possible solution, print “Neibb”.

Scoring

Group

Points

Constraints

1

20

$n \leq 5$

2

30

$n \leq 10$

3

27

$n \leq 20$

4

23

No further constraints

Sample Input 1 Sample Output 1
3
2 2 3
3 1 2 3
3 1 2 3
3 2 1
Sample Input 2 Sample Output 2
4
3 2 3 4
4 1 2 3 4
4 1 2 3 4
3 2 3 4
2 4 3 1
Sample Input 3 Sample Output 3
5
2 3 4
2 4 5
2 1 3
2 3 4
1 5
Neibb

Please log in to submit a solution to this problem

Log in