거울대칭트리 그래프

시간 제한1초메모리 제한128 MB

요약
루트를 제외한 모든 리프에서 트리와 그 거울 복사본을 이어붙여 만든 대칭 트리 그래프인지 판별합니다.
난이도

보통10점 중 6점

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

문제

T는 루트가 정해진 트리이고, S는 T와 완전히 같은 복사본이다. 두 트리에서 루트를 제외한 각 단말 정점을 서로 대응되는 정점끼리 하나로 합친다. 이렇게 얻은 그래프를 거울대칭트리 그래프라고 한다.

무방향 연결 그래프가 주어졌을 때, 이 그래프가 거울대칭트리 그래프인지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 그래프의 정점은 1부터 N까지 번호가 매겨져 있다.

다음 M개의 줄에는 간선 하나를 나타내는 두 정수 x와 y가 주어진다. x와 y는 서로 다른 정점이며, 두 정점 사이에는 간선이 많아야 하나만 존재한다.

출력

주어진 그래프가 거울대칭트리 그래프이면 YES를, 아니면 NO를 출력한다.

제한

  • 3 ≤ N, M ≤ 100,000
  • 1 ≤ x, y ≤ N
  • x ≠ y

예제3

  1. 예제 1

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

  2. 예제 2

    입력
    6 6
1 2
2 3
2 4
3 5
4 5
5 6
    예상 출력
    YES

  3. 예제 3

    입력
    22 28
13 8
8 1
1 22
1 12
1 14
13 18
13 4
4 20
20 7
13 15
15 3
15 9
9 16
9 19
22 5
12 5
14 5
5 11
11 6
18 6
7 10
10 17
17 6
3 21
21 6
16 2
19 2
2 21
    예상 출력
    YES