시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB190191813.139%

문제

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가 이어져 있는 것이다. 두 정점 사이에는 많아야 하나의 간선만 있을 수 있다.

출력

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

제한

  • 3 ≤ N, M ≤ 100,000

예제 입력 1

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

예제 출력 1

NO

예제 입력 2

6 6
1 2
2 3
2 4
3 5
4 5
5 6

예제 출력 2

YES

예제 입력 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

예제 출력 3

YES
W3sicHJvYmxlbV9pZCI6IjI0MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWM2YjhcdWIzMDBcdWNlNmRcdWQyYjhcdWI5YWMgXHVhZGY4XHViNzk4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5UXHViMjk0IFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBTXHViMjk0IFRcdWM3NTggXHVjNjQ0XHViY2JkXHVkNTVjIFx1YmNmNVx1YzBhY1x1YmNmOFx1Yzc3NFx1YjJlNC4gXHVjNzkwIFx1Yzc3NFx1YzgxYyBUXHVjNjQwIFNcdWI5N2MgXHVkNTY5XHVjZTVjXHViMmU0LiBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWIyZThcdWI5ZDAgXHViMTc4XHViNGRjIChsZWFmIG5vZGUpXHViOTdjIFx1ZDU2OVx1Y2U1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVhYzcwXHVjNmI4XHViMzAwXHVjZTZkXHVkMmI4XHViOWFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVhYzcwXHVjNmI4XHViMzAwXHVjZTZkXHVkMmI4XHViOWFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZjRhNjY3NDMtZGFhMS00MWZmLTk3MWItZjNiNWEyOWI2MmFhXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzMDBweDsgaGVpZ2h0OiAyNThweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoeCAmbmU7IHksIDEgJmxlOyB4LCB5ICZsZTsgTikgeFx1YzY0MCB5XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NzRcdWFjZTAsIHhcdWM2NDAgeVx1YWMwMCBcdWM3NzRcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzgxMCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWI5Y2MgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVhYzcwXHVjNmI4XHViMzAwXHVjZTZkXHVkMmI4XHViOWFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YmE3NCA8Y29kZT5ZRVM8XC9jb2RlPlx1Yjk3YyBcdWM1NDRcdWIyYzhcdWJhNzQgPGNvZGU+Tk88XC9jb2RlPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjMgJmxlOyBOLCBNICZsZTsgMTAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjQzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyZWUgTWlycm9yaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5MZXQgVCBiZSBhIHJvb3RlZCB0cmVlIChhIGNvbm5lY3RlZCB1bmRpcmVjdGVkIGFjeWxpYyBncmFwaCksIGFuZCBsZXQgUyBiZSBhIHBlcmZlY3QgY29weSBvZiBULiBDb25zdHJ1Y3QgYSBuZXcgZ3JhcGggYnkgdGFraW5nIHRoZSB1bmlvbiBvZiBUIGFuZCBTLCBhbmQgbWVyZ2luZyB0aGUgY29ycmVzcG9uZGluZyBsZWFmIG5vZGVzIChidXQgbmV2ZXIgdGhlIHJvb3QpLiBXZSBjYWxsIHN1Y2ggYSBncmFwaCBhIHRyZWUtbWlycm9yZWQgZ3JhcGguPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaWYgYW4gYXJiaXRyYXJ5IHVuZGlyZWN0ZWQgY29ubmVjdGVkIGdyYXBoIGlzIGEgdHJlZS1taXJyb3JlZCBncmFwaC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mNGE2Njc0My1kYWExLTQxZmYtOTcxYi1mM2I1YTI5YjYyYWFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMwMHB4OyBoZWlnaHQ6IDI1OHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMTogQW4gZXhhbXBsZSBvZiBhIHRyZWUtbWlycm9yZWQgZ3JhcGguIFRoZSBmaWd1cmUgY29ycmVzcG9uZHMgdG8gdGhlIHRoaXJkIGV4YW1wbGUgdGVzdCBjYXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCBlZGdlcyBvZiBhIGdyYXBoIEcuIFRoZSB2ZXJ0aWNlcyBpbiBHIGFyZSBsYWJlbGVkIGZyb20gMSB0byBOLiBUaGUgZm9sbG93aW5nIE0gbGluZXMgZGVzY3JpYmUgdGhlIGVkZ2VzLiBFYWNoIHN1Y2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSAoeCAmbmU7IHk7IDEgJmxlOyB4LCB5ICZsZTsgTiksIGRlc2NyaWJpbmcgb25lIGVkZ2UuIFRoZXJlIHdpbGwgYmUgYXQgbW9zdCBvbmUgZWRnZSBiZXR3ZWVuIGFueSBwYWlyIG9mIHZlcnRpY2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIHN0cmluZyA8Y29kZT5ZRVM8XC9jb2RlPiBpZiB0aGUgZ3JhcGggRyBpcyBhIHRyZWUtbWlycm9yZWQgZ3JhcGgsIGFuZCA8Y29kZT5OTzxcL2NvZGU+IG90aGVyd2lzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjMgJmxlOyBOLCBNICZsZTsgMTAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 8번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: kareus