22969번 - 대나무숲

정휘는 대나무를 다음과 같이 정의했다. (실제 Graph Theory에서 사용하는 용어인 Bamboo Tree와는 차이가 있다.)

• 대나무는 트리의 한 종류이다.
• 가운데 길이가 3 이상인(3개 이상의 간선으로 구성된) 기둥이 있다.
• 기둥에 속한 정점에서 양쪽으로 정점이 뻗어있을 수 있다.
• 이때 기둥에 속한 정점에서 1개 혹은 3개 이상의 정점이 뻗어나갈 수 없다. (0개 혹은 2개만 가능하다.)
• 모든 정점은 기둥과의 거리가 1 이하가 되어야 한다.

대나무숲이란, 대나무로만 구성된 포레스트를 의미한다.

그래프가 주어지면 대나무숲인지 확인해보자.

예제 2는 2번 정점에서 1개의 정점만 뻗어나갔기 때문에 대나무숲이 아니다.

예제 4는 2번 정점에서 3개의 정점이 뻗어나갔기 때문에 대나무숲이 아니다.

예제 5는 3번 정점에서 뻗어나간 정점 중 기둥과 거리가 2 이상인 정점이 있기 때문에 대나무숲이 아니다.

예제 6은 길이가 3 이상인 기둥이 존재하지 않기 때문에 대나무숲이 아니다.

예제 8은 포레스트가 아니다.

첫째 줄에 정점의 개수와 간선의 개수를 의미하는 정수 $N, M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐, 각 간선이 연결하는 두 정점 $u, v$가 공백으로 구분되어 주어진다.

입력으로 주어진 그래프가 대나무숲이라면 TAK, 대나무숲이 아니라면 NIE를 출력한다.

• $1 \leq N \leq 100\,000$
• $1 \leq M \leq 200\,000$
• $1 \leq u, v \leq N$
• 같은 정점을 연결하는 간선은 주어지지 않는다.
• 중복된 간선이 주어지지 않는다.