Description

给你 $n$ 个点和 $m$ 条双向边，问能否将其中的一些边改成有向边，使得只考虑有向边的情况下每个点的入度都为 $1$ 。

Input Format

第一行输入 $n,m(1≤n≤100000,1≤m≤200000)$ ，接下来 $m$ 行每行两个数 $a,b$ 表示点 $a$ 和点 $b$ 之间有一条双向边。输入保证没有重边与自环。

Output Format

若没有合法方案，输出 $\verb!NIE!$，否则先在第一行输出 $\verb!TAK!$，然后在第 $i+1$ 行输出点 $i$ 的入度是由哪个点出发的边所得到的。

感谢@hdxrie 提供的翻译。

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

TAK
3
3
4
1

4 3
1 3
3 4
2 3

NIE