/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
パ研合宿2020ではレクリエーションの一環として、N 人の人 1\ldots N を呼んで 1 人ずつ順番にアニマルショーをさせることにしました。
人 i は A_i 種類の動物 a_{i,1},\ a_{i,2},\ldots,\ a_{i,{A_i}} を使ってショーを行います。ここで、動物の種類は 1 以上 5×10^5 以下の整数で表されます。
ところで、アニマルショーを行うにあたっては動物アレルギーを持つ人の安全を確保する必要があります。ショーをさせる人達にアンケートをしたところ、以下の事実が分かりました。
- 人 i は B_i 種類の動物 b_{i,1},\ b_{i,2},\ldots,\ b_{i,B_i} に対してアレルギーを持っている。
人 i が動物 X へのアレルギーを持っている場合、人 i よりも前にショーを行う人が 1 人でも動物 X を使用しているとアレルギー反応を起こしてしまいます。全ての人がアレルギーを起こさないようなショーの順番が存在するか判定し、存在するならそのうちの 1 つを出力してください。
全ての人は自身のショーで使用する動物へのアレルギーを持っていないことが保証されます。
制約
- 1\leq N\leq2×10^5
- 1\leq A_i,\ B_i
- 1\leq \sum A_i\leq5×10^5
- 1\leq \sum B_i\leq5×10^5
- 1\leq a_{i,j}\leq5×10^5
- 1\leq b_{i,j}\leq5×10^5
- a_{i,j}≠a_{i,k}\ (j≠k)
- b_{i,j}≠b_{i,k}\ (j≠k)
- a_{i,j}≠b_{i,k}
- 入力は全て整数
小課題
- (50 点) N\leq8,\ \sum A_i\leq100,\ \sum B_i\leq100,\ a_{i,j}\leq100,\ b_{i,j}\leq100
- (100 点) N\leq9,\ \sum A_i\leq2000,\ \sum B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000
- (100 点) N\leq1000,\ \sum A_i\leq2000,\ \sum B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000
- (250 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
\(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}\)
出力
条件を満たすショーの順番が存在する場合、i 番目に人 P_i がショーを行うとして i の昇順に P_i を空白区切りで出力してください。順番が存在しない場合は -1 を出力してください。
ジャッジの都合上末尾の改行を忘れていたり、末尾に余分な空白が入っていたりすると不正解となります。注意してください。
入力例1
2 2 1 2 1 3 2 1 3 1 4
出力例1
1 2
ショーの順番を逆にした場合、人 1 が動物 3 に対するアレルギー反応を起こしてしまいます。
このサンプルは全ての小課題の制約を満たします。
入力例2
2 2 1 2 2 3 4 2 3 4 2 1 2
出力例2
-1
どのような順番でショーをしても、いずれかの人がアレルギー反応を起こしてしまいます。
このサンプルは全ての小課題の制約を満たします。
入力例3
3 3 1 3 4 2 2 5 2 1 8 2 9 7 2 3 8 2 1 4
出力例3
3 2 1
このサンプルは全ての小課題の制約を満たします。
Writer : penguinman