아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

대나무숲

시간 제한3초메모리 제한1024 MB

요약
그래프가 주어질 때, 각 연결 성분이 대나무, 즉 길이 3 이상인 줄기를 가지고 줄기 위의 각 정점에 잎이 0개 또는 2개 붙으며 모든 정점이 줄기에서 거리 1 이내인 나무인지 판정한다.
난이도

보통10점 중 7점

유형
그래프, 트리, DFS, 구현
정답자
아직 제출이 없습니다

문제

정휘는 대나무를 다음과 같이 정의했다. (그래프 이론에서 쓰이는 Bamboo Tree와는 다르다.)

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

대나무숲이란 대나무로만 이루어진 포레스트를 말한다.

그래프가 주어지면 대나무숲인지 판별하자.

예제 2는 2번 정점에서 정점 1개만 뻗어나갔으므로 대나무숲이 아니다.

예제 4는 2번 정점에서 정점 3개가 뻗어나갔으므로 대나무숲이 아니다.

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

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

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

입력

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

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

출력

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

제한

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

예제5

  1. 예제 1

    입력
    7 6
1 2
2 3
3 4
4 5
3 6
3 7
    예상 출력
    TAK

  2. 예제 2

    입력
    5 4
1 2
2 3
3 4
2 5
    예상 출력
    NIE

  3. 예제 3

    입력
    9 8
1 2
2 3
3 4
4 5
1 6
1 7
5 8
5 9
    예상 출력
    TAK

  4. 예제 4

    입력
    7 6
1 2
2 3
3 4
2 5
2 6
2 7
    예상 출력
    NIE

  5. 예제 5

    입력
    9 8
1 2
2 3
3 4
4 5
3 6
6 7
3 8
8 9
    예상 출력
    NIE