Problem Description

Score: $ 500 $ points

At the Paken Camp 2020, as part of the recreational activities, they decided to call $ N $ people $1\ldots\ N$ to perform an animal show one by one in order.

Person $ i $ will perform a show using $ A_i $ types of animals $a_{i,1},\ a_{i,2},\ldots,\ a_{i,{A_i}}$. Here, the types of animals are represented by integers between $ 1 $ and $ 5×10^5 $.

However, to ensure the safety of people with animal allergies, it is necessary to prevent allergic reactions. An inquiry was conducted among the people performing the show, and the following facts were revealed:

• Person $ i $ is allergic to $ B_i $ types of animals $b_{i,1},\ b_{i,2},\ldots,\ b_{i,B_i}$.

If person $ i $ is allergic to animal $ X $, they will have an allergic reaction if any person performing the show before them uses animal $ X $. Determine if there exists an order of the show where no one has an allergic reaction, and if so, output one such order.

It is guaranteed that no person is allergic to the animals they use in their own show.

Input Format

The input is given from the standard input in the following format:

\(N\)
\(A_1\)
\(a_{1,1}\) \(a_{1,2}\) \(\ldots\) \(a_{1,A_1}\)
\(B_1\)
\(b_{1,1}\) \(b_{1,2}\) \(\ldots\) \(b_{1,B_1}\)
\(A_2\)
\(a_{2,1}\) \(a_{2,2}\) \(\ldots\) \(a_{2,A_2}\)
\(B_2\)
\(b_{2,1}\) \(b_{2,2}\) \(\ldots\) \(b_{2,B_2}\)
\(︙\)
\(A_N\)
\(a_{N,1}\) \(a_{N,2}\) \(\ldots\) \(a_{N,A_N}\)
\(B_N\)
\(b_{N,1}\) \(b_{N,2}\) \(\ldots\) \(b_{N,B_N}\)

Output Format

If there exists an order of the show that satisfies the conditions, output the order such that person $ P_i $ performs the show in the $ i $-th position, in ascending order of $ i $, separated by spaces. If no such order exists, output $ -1 $.

Note that forgetting a trailing newline or having extra trailing spaces at the end will result in an incorrect answer. Be careful.

Sample Input and Output

Sample Input #1

2
2
1 2
1
3
2
1 3
1
4

Sample Output #1

1 2

Sample Input #2

2
2
1 2
2
3 4
2
3 4
2
1 2

Sample Output #2

-1

Sample Input #3

3
3
1 3 4
2
2 5
2
1 8
2
9 7
2
3 8
2
1 4

Sample Output #3

3 2 1

Notes/Hints

Subtasks

1. $ (50 $ points$ ) $ $N\leq8,\ \sum\ A_i\leq100,\ \sum\ B_i\leq100,\ a_{i,j}\leq100,\ b_{i,j}\leq100$
2. $ (100 $ points$ ) $ $N\leq9,\ \sum\ A_i\leq2000,\ \sum\ B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000$
3. $ (100 $ points$ ) $ $N\leq1000,\ \sum\ A_i\leq2000,\ \sum\ B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000$
4. $ (250 $ points$ ) $ No additional constraints.

见题面 Input 部分

见题面 Output 部分