[AdditionalFile5643.zip](file://AdditionalFile5643.zip?type=additional_file)

#5643. 「PA 2014 Final」Budowa

标签: 传统 | 时间限制: 100 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Final Budowa

Bajtazar 想在比特托邦建造一个赛车场。为了争夺建设资金，他正与 Bajtymon 竞争，后者更倾向于建造一个滑雪跳台。这两个项目都耗资巨大，因此 Bajtazar 和 Bajtymon 都在争取比特托邦国王的资助。

国王现在必须在两个选项中做出选择：要么资助赛车场，要么资助滑雪跳台。为此，他将咨询首席顾问（Naczelny Doradca），首席顾问是国王顾问层级的首领。每个顾问要么是专家，能够独立给出建议；要么是团队领导者，负责管理一个顾问团队。团队领导者所提出的建议必须与其团队中多数成员的意见保持一致。幸运的是，每个团队中的顾问人数都是奇数。因此，最终的决定完全取决于专家们（即不领导任何团队的顾问）的看法。除首席顾问外，每位顾问都恰好有一名直属上司。

Bajtazar 和 Bajtymon 并没有坐以待毙。他们都在努力说服专家支持自己的主张。这并非易事——说服一名专家需要整整一天的时间。一旦专家被说服，他就不会再改变主意。当然，也可能存在一些专家在初始时就已经有了明确且不可更改的立场。

每天拂晓时分，Bajtazar 会选择一名尚未表态的专家并前往游说。Bajtymon 不喜欢起得太早，因此他选择要说服的专家的时间会稍晚一些（也因此他会失去游说那些已经被 Bajtazar 选中的专家的机会）。双方的行动会一直持续到所有专家都明确了立场为止。Bajtazar 和 Bajtymon 都非常清楚国王顾问的层级结构。Bajtazar 想知道，他是否能制定一个游说计划，使得无论 Bajtymon 如何行动，首席顾问最终都会建议建造赛车场？

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 1000)$，表示顾问的总数。顾问的编号为从 $1$ 到 $n$。编号为 $1$ 的顾问是首席顾问。

接下来的 $n$ 行中，第 $i$ 行包含对第 $i$ 个顾问的描述。该描述以一个整数 $c_{i}$ $(-2 \leq c_{i} \leq n)$ 开头：

• 如果 $c_{i} \leq 0$，则该顾问是一名专家（此时该行的描述仅包含 $c_{i}$ 这一数字）。其中，$c_{i}$ 取值 $-2$、$-1$ 和 $0$ 分别表示：支持建造赛车场、支持建造滑雪跳台、尚未表态。
• 如果 $c_{i} \geq 1$，则 $c_{i}$ 为一个奇数，表示顾问 $i$ 领导着一个由 $c_{i}$ 名成员组成的顾问团队。在该行随后的部分将依次列出这些团队成员的编号。

每个编号大于 $1$ 的顾问都恰好属于一个团队。

输出格式

如果 Bajtazar 无法通过说服专家来确保首席顾问建议建造赛车场，请输出 NIE。

否则，请输出两行内容。第一行包含 TAK 以及一个整数 $d$，其中 $d$ 表示 Bajtazar 在第一天有多少种选择专家的方案，能够确保他在后续几天采取最优决策时，一定能获得首席顾问对建造赛车场的建议。

第二行应按升序输出这 $d$ 名专家的编号。如果初始状态下首席顾问就已经确定会建议建造赛车场（即无需说服任何专家），则输出 $d=0$。

样例

输入

4
3 2 3 4
-2
0
-1

输出

TAK 1
3