C-조류

C-조류(C-algae) 는 비테오시아 사람들이 가장 좋아하는 전통 요리이다. C-조류는 다음과 같이 재귀적으로 정의되는 매우 독특한 구조를 가진다.

• 세포 하나로 이루어진 조류는 C-조류이다.
• 두 C-조류 $K_1$ 과 $K_2$ 는 다음 두 가지 방법 중 정확히 한 가지로 합쳐져 새로운 C-조류 $K$ 가 된다.

  1. 분리 합집합 — $K_1$ 과 $K_2$ 의 모든 세포와 모든 연결을 그대로 가져온다.

     

  2. 조인(join) — $K_1$ 과 $K_2$ 의 모든 세포와 모든 연결을 가져온 뒤, 추가로 $K_1$ 의 모든 세포를 $K_2$ 의 모든 세포와 각각 연결한다.

     

최근 적대국 비토시아가 진짜 C-조류와 구별하기 매우 어려울 만큼 비슷한 가짜 조류를 팔기 시작했다. 이에 비테오시아 정부는 주어진 조류가 실제로 C-조류인지 검증하는 프로그램을 요청하였다.

여러 조류의 정보를 표준 입력에서 읽어, 각각이 올바른 C-조류인지 판별하여 표준 출력에 답을 출력하는 프로그램을 작성하라. 모든 연결은 방향이 없다.

첫째 줄에 검사할 조류의 개수 $k$ ($1 \le k \le 10$) 가 주어진다. 이어서 $k$ 개 조류의 정보가 주어진다.

각 조류의 정보는 먼저 세포의 수 $n$ 과 연결의 수 $m$ ($1 \le n \le 10\,000$, $0 \le m \le 100\,000$) 이 공백으로 구분되어 한 줄에 주어진다. 세포는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 이어지는 $m$ 개의 줄에는 각각 두 정수 $a$, $b$ ($a \ne b$, $1 \le a, b \le n$) 가 주어지며, 이는 세포 $a$ 와 세포 $b$ 가 방향 없이 연결되어 있음을 뜻한다. 각 연결은 정확히 한 번만 주어진다.

$k$ 개의 줄을 출력한다. $i$ 번째 줄에는 다음을 출력한다.

• $i$ 번째 조류가 올바른 C-조류이면 TAK,
• 그렇지 않으면 NIE.