시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 5 3 10.345%

문제

T는 루트가 있는 트리이다. S는 T의 완벽한 복사본이다. 자 이제 T와 S를 합친다. 루트를 제외한 모든 단말 노드 (leaf node)를 합치면 된다. 이 그래프는 거울대칭트리 그래프이다.

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

입력

첫째 줄에 N과 M이 주어진다. N은 정점의 개수 M은 간선의 개수이다. 그래프의 정점은 1부터 N까지 번호가 매겨져 있다. 다음 M개의 줄에는 x와 y가 주어진다. (x≠y, 1<=x,y<=N) x와 y는 하나의 간선이고, x와 y가 이어져 있는 것이다. 두 정점 사이에는 많아야 하나의 간선만 있을 수 있다. (3<=N,M<=100,000)

출력

첫째 줄에 그래프가 거울대칭트리 그래프이면 YES를 아니면 NO를 출력한다.

예제 입력

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

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 8번