Toll

Memory limit: 32 MB

King Byteasar has yielded under pressure of Byteotian merchants and hence decided to settle the issue of toll paid by them. Byteotia consists of towns connected with bidirectional roads. Each road connects directly two different towns and no two towns are connected by more than one direct road. Note that the roads may lead through tunnels or flyovers.

Until now each town in Byteotia imposed duty on everyone who either entered or left the town. The merchants, discontented with such situation, lodged a protest against multiple taxation. King Byteasar ruled that the town privileges are now restricted. According to the new royal edict, each town can only charge toll on merchants travelling by exact one road leading into the town, regardless of the direction they are travelling in. Furthermore, for each road, those who travel it cannot be made to pay the duty to both towns the road connects. It remains to determine which town should collect toll from which road. Solving this problem His Highness has commissioned to you.

Task

Write a programme that:

• reads the Byteotian road system's description from the standard input,
• for each town determines on which road it should impose toll, or claims it is impossible,
• writes out the result to the standard output.

Input

There are two integers in the first line of the standard input: and (, ), denoting the number of towns and roads in Byteotia, respectively. The towns are numbered from to . In next lines descriptions of the roads follow. In line no. there are two integers and () meaning that towns and are directly connected by a road.

Output

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 lines should tell which city collects toll from which road. Line no. should tell on which road the town no. imposes toll. Since town no. is obviously one endpoint of this road, it is enough to tell what is the other endpoint. Thus if the town no. imposes toll on the road connecting it with the town no. , the line no. should contain the number . If more than one solution exists, write out one chosen arbitrarily.

Example

For the input data:

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

the correct result is:

TAK
3
3
4
1

The arrows in the figure point to towns that collect toll from merchants using the road. Observe that the merchants who follow the road connecting the towns 1 and 2 are not charged with toll at all.

For the input data:

4 3
1 3
3 4
2 3

the correct result is:

NIE

Task author: Michal Pilipczuk.