There are $n$ gnomes at a New Year's party. The gnomes would like to have nice memories of this party, so they invited a photographer to take a photo of each gnome with their friends. Every gnome (except for Grumpy and Happy, who do not care, though each for different reasons) would like to stand exactly in the middle of their photo (fortunately, every gnome has an even number of friends).

However, this is not so simple, because the photographer also has his own artistic vision for the photos. He brought $n$ pointed hats of different heights from $1$ to $n$ and announced that each gnome must wear one of them, and furthermore, in every photo, the gnomes must stand in order of increasing hat height.

The gnomes began to wonder which of them should get which hat so that their wishes and the photographer's vision could be fulfilled.

Input

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 500\,000$, $0 \le m \le 500\,000$) denoting the number of gnomes and the number of pairs of friends. For simplicity, the gnomes are numbered from $1$ to $n$, and the numbers of Grumpy and Happy are $1$ and $2$, respectively.

The next $m$ lines describe the pairs of friends: each contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \neq b$) meaning that gnomes $a$ and $b$ are friends with each other. Each gnome has an even number of friends.

Output

In the first line of the output, your program should print one word TAK or NIE, depending on whether it is possible to assign hats to the gnomes. If the answer is positive, then in the second line, you should print a sequence of $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$), separated by single spaces; the number $h_i$ denotes the height of the hat assigned to gnome number $i$. If there is more than one correct answer, your program may print any of them.

Examples

Input 1

6 7
5 6
1 4
4 5
5 3
1 5
3 2
2 6

Output 1

TAK
1 6 5 2 3 4

Subtasks

Test cases

• $n = 5$, everyone is friends with everyone; answer: NIE;
• $n = 1000$, every gnome has two friends; answer: TAK;
• $n = 500\,000$, every gnome has two friends; answer: TAK.