#P3708. [Poi96]赌博机

    ID: 2911 传统题 1000ms 256MiB 尝试: 25 已通过: 2 难度: 7 上传者: 标签>CF2200提高欧拉路径不变量分析深度优先搜索直接模拟

[Poi96]赌博机

题目描述

一台机器有 nn 个整数生成器 G1,…,GnG_1,\dots,G_n。第 ii 个生成器有一个初始集合 Si⊆{1,…,n}S_i\subseteq\{1,\dots,n\},集合可以为空。

机器从 G1G_1 开始。每次激活 GiG_i 时,如果 SiS_i 中还有尚未生成过的数字,就任选其中一个正整数 rr 输出,并激活 GrG_r。同一生成器中的数字至多使用一次。如果当前生成器已经用完自己集合里的数字,它输出 00,游戏立即结束。

当且仅当最后输出 00 的是 GnG_n,并且此时所有生成器都用尽了各自的集合,这次游戏才算失败。即使所有集合均已用尽,只要是在其他生成器处结束,这次游戏仍然成功。

请判断是否存在一次成功的游戏,如果存在,输出任意一组机器依次生成的数字。

输入格式

第一行一个正整数 nn(1≤n≤10001\le n\le1000)。

接下来 nn 行,第 ii 行先给出一个整数 kik_i(0≤ki≤n0\le k_i\le n),然后给出 SiS_i 的 kik_i 个不同的元素。保证 ∑iki≤12000\sum_i k_i\le12000。

输出格式

若所有游戏都会失败,输出单词 NIE。否则输出一行由空格分隔的整数,依次为一次成功游戏所生成的所有数字,包括结尾的 00。

样例

2
2 1 2
1 2
2 2 0
2
1 2
0
NIE

波兰信息学奥林匹克组委会原题