Guilds

King Byteasar faces a serious matter. Two competing trade organisations, the Tailors' Guild and the Sewers' Guild, have at the same time asked for permission to open offices in the towns of his kingdom.

Byteotia has $n$ towns, some of them joined by bidirectional roads. Each town may host an office of the Tailors' Guild, an office of the Sewers' Guild, or no office at all. To keep both guilds satisfied, the placement must obey the following rule for each guild independently: every town must either

• host an office of that guild, or
• be directly connected by a road to a town that hosts an office of that guild.

The king, however, suspects foul play. If a single town were to host the offices of both guilds at once, it could lead to a clothing cartel, so he forbids any town from hosting both offices.

Determine whether the offices can be placed according to these rules.

The first line contains two integers $n$ and $m$ ($1 \le n \le 200{,}000$, $0 \le m \le 500{,}000$): the number of towns and the number of roads in Byteotia. The towns are numbered from $1$ to $n$.

Each of the next $m$ lines describes one road with two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), meaning that the $i$-th road connects towns $a_i$ and $b_i$. Every pair of towns is joined by at most one road. Roads meet only at towns (they may pass through tunnels or overpasses) and never cross elsewhere.

Print a single line: TAK if the offices can be placed according to the rules, or NIE otherwise. (TAK and NIE mean "yes" and "no" in Polish.)

In the illustration, the towns where a Tailors' Guild office should open are marked with circles, and the towns where a Sewers' Guild office should open are marked with rhombi.