[POI2010] GIL-Guilds

题目描述

给一张无向图，要求你用黑白灰给点染色，且满足对于任意一个黑点，至少有一个白点和他相邻；对于任意一个白点，至少有一个黑点与他相邻，对于任意一个灰点，至少同时有一个黑点和白点和灰点与他相邻，问能否成功

输入格式

两个整数n（1<=n<=200000）和m（1<=m<=500000），n代表点数，m代表边的总数

接下来m行每行两个整数ai和bi，表示城市ai和城市bi有道路相接。不会有重边。

输出格式

如果可以染色成功输出TAK（波兰语的Yes），否则输出NIE（波兰语的No）。

样例 #1

样例输入 #1

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

样例输出 #1

TAK