길드

비테아사르 왕에게 골치 아픈 일이 생겼다. 서로 경쟁하는 두 상인 조직, 재단사 길드와 재봉사 길드가 동시에 왕국의 여러 마을에 사무소를 열게 해 달라고 요청했다.

비테오티아에는 $n$개의 마을이 있고, 그중 일부는 양방향 도로로 이어져 있다. 각 마을에는 재단사 길드 사무소나 재봉사 길드 사무소를 둘 수 있고, 아무 사무소도 두지 않을 수도 있다. 두 길드를 모두 만족시키려면 각 길드에 대해 독립적으로 다음 규칙을 지켜야 한다. 즉, 모든 마을은

• 그 길드의 사무소를 직접 두고 있거나,
• 그 길드의 사무소가 있는 마을과 도로로 직접 연결되어 있어야 한다.

한편 왕은 부정을 의심하고 있다. 한 마을이 두 길드의 사무소를 동시에 두면 의류 카르텔이 생길 수 있으므로, 어떤 마을도 두 사무소를 동시에 두지 못하게 한다.

이 규칙에 맞게 사무소들을 배치할 수 있는지 판단하라.

첫째 줄에 두 정수 $n$과 $m$ ($1 \le n \le 200{,}000$, $0 \le m \le 500{,}000$)이 주어진다. 각각 비테오티아의 마을 수와 도로 수를 뜻한다. 마을은 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 도로가 하나씩 주어진다. $i$번째 줄에는 두 정수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 있으며, $i$번째 도로가 마을 $a_i$와 $b_i$를 잇는다는 뜻이다. 임의의 두 마을을 잇는 도로는 많아야 하나뿐이다. 도로는 마을에서만 만나며(터널이나 고가도로로 지날 수 있다), 마을 밖에서는 서로 교차하지 않는다.

규칙에 맞게 사무소를 배치할 수 있으면 TAK을, 그렇지 않으면 NIE를 한 줄에 출력하라. (TAK과 NIE는 폴란드어로 각각 "예"와 "아니오"를 뜻한다.)

그림에서 재단사 길드 사무소를 두는 마을은 원으로, 재봉사 길드 사무소를 두는 마을은 마름모로 표시되어 있다.