AT_pakencamp_2020_day2_d Animal Show

题目描述

在パ研合宿2020的娱乐活动中，我们决定邀请 $N$ 个人依次进行动物表演。每个参与者 $i$ 将使用 $A_i$ 种动物 $a_{i,1}, a_{i,2}, \ldots, a_{i,A_i}$ 进行表演。动物的种类用整数 $1$ 到 $5 \times 10^5$ 表示。然而，为了确保对动物过敏的人的安全需引起重视。调查显示： - 参与者 $i$ 对 $B_i$ 种动物 $b_{i,1}, b_{i,2}, \ldots, b_{i,B_i}$ 过敏。如果参与者 $i$ 对某一种动物 $X$ 过敏，并且在他之前已有任何人使用过动物 $X$，那么 $i$ 就会发生过敏反应。请你判定是否存在一种表演顺序，使得所有参与者都不会发生过敏反应。如果存在，请给出一个符合条件的顺序；如果没有，输出 $-1$。题目保证每个人对自己表演中使用的动物没有过敏。

输入格式

输入由以下格式提供： ``` $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}$ $\vdots$ $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}$ ```

输出格式

如果存在不引发过敏反应的表演顺序，按照顺序用空格分隔输出每个演出者的编号 $P_i$。如果不存在这样的顺序，输出 $-1$。

说明/提示

### 子任务 1. (50 点) $N \leq 8, \sum A_i \leq 100, \sum B_i \leq 100, a_{i,j} \leq 100, b_{i,j} \leq 100$ 2. (100 点) $N \leq 9, \sum A_i \leq 2000, \sum B_i \leq 2000, a_{i,j} \leq 2000, b_{i,j} \leq 2000$ 3. (100 点) $N \leq 1000, \sum A_i \leq 2000, \sum B_i \leq 2000, a_{i,j} \leq 2000, b_{i,j} \leq 2000$ 4. (250 点) 无其他限制。 **本翻译由 AI 自动生成**