# [POI2008]CLO-Toll

## 题意翻译

**题目描述：** 给你 \$n\$ 个点和 \$m\$ 条双向边，问能否将其中的一些边改成有向边，使得只考虑有向边的情况下每个点的入度都为 \$1\$ 。 **输入格式:** 第一行输入 \$n,m(1≤n≤100000,1≤m≤200000)\$ ，接下来 \$m\$ 行每行两个数 \$a,b\$ 表示点 \$a\$ 和点 \$b\$ 之间有一条双向边。输入保证没有重边与自环。 **输出格式：** 若没有合法方案，输出 \$NIE\$ ，否则先在第一行输出 \$TAK\$ ，然后在第 \$i+1\$ 行输出点 \$i\$ 的入度是由哪个点出发的边所得到的。 感谢@hdxrie 提供的翻译

## 输入输出格式

### 输入格式

There are two integers in the first line of the standard input: \$n\$ and \$m\$ (\$1 \le n \le 100\ 000\$, \$1 \le n \le 200\ 000\$), denoting the number of towns and roads in Byteotia, respectively. The towns are numbered from \$1\$ to \$n\$. In next \$m\$ lines descriptions of the roads follow. In line No. \$i\$ there are two integers \$a_i\$ and \$b_i\$ () meaning that towns \$a_i\$ and \$b_i\$ are directly connected by a road.

### 输出格式

If collecting the toll in accordance with the royal edict is impossible, your programme should write the word NIE ('no' in Polish) in the first and only line of the standard output. Otherwise, it should write the word TAK ('yes' in Polish) in the first line, while in the following \$n\$ lines should tell which city collects toll from which road. Line no. \$(i+1)\$ should tell on which road the town no. \$i\$ imposes toll. Since town no. \$i\$ is obviously one endpoint of this road, it is enough to tell what is the other endpoint. Thus if the town no. \$i\$ imposes toll on the road connecting it with the town no.\$j\$ , the line no. \$(i+1)\$ should contain the number \$j\$. If more than one solution exists, write out one chosen arbitrarily.

## 输入输出样例

### 输入样例 #1

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

### 输出样例 #1

``````TAK
3
3
4
1``````

### 输入样例 #2

``````4 3
1 3
3 4
2 3``````

### 输出样例 #2

``NIE``