홀수 길이 사이클

무방향 그래프가 주어질 때, 그 그래프 안에 홀수 길이의 사이클이 존재하는지 판별하는 문제이다.

먼저 테스트 케이스의 개수 $t$가 주어지고, 이어서 $t$개의 그래프가 주어진다. 각 그래프마다 홀수 길이의 사이클이 존재하는지 판단하면 된다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 그다음 $t$개의 무방향 그래프 정보가 이어진다.

각 그래프 정보는 정점의 수 $n$과 간선의 수 $m$으로 시작한다 ($1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$). 이어지는 $m$개의 줄에는 각각 하나의 간선을 나타내는 두 정수가 주어지며, 두 정수는 모두 $1$ 이상 $n$ 이하로 간선의 두 끝점을 뜻한다.

각 그래프마다 한 줄에 답을 출력한다. 그래프에 홀수 길이의 사이클이 존재하면(즉, 그래프가 이분 그래프가 아니면) TAK을 출력하고, 존재하지 않으면 NIE를 출력한다.