시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 169 26 16 16.162%

문제

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를 출력한다.

예제 입력 1

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

예제 출력 1

YES

힌트

W3sicHJvYmxlbV9pZCI6IjI0MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWM2YjhcdWIzMDBcdWNlNmRcdWQyYjhcdWI5YWMgXHVhZGY4XHViNzk4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5UXHViMjk0IFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBTXHViMjk0IFRcdWM3NTggXHVjNjQ0XHViY2JkXHVkNTVjIFx1YmNmNVx1YzBhY1x1YmNmOFx1Yzc3NFx1YjJlNC4gXHVjNzkwIFx1Yzc3NFx1YzgxYyBUXHVjNjQwIFNcdWI5N2MgXHVkNTY5XHVjZTVjXHViMmU0LiBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWIyZThcdWI5ZDAgXHViMTc4XHViNGRjIChsZWFmIG5vZGUpXHViOTdjIFx1ZDU2OVx1Y2U1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVhYzcwXHVjNmI4XHViMzAwXHVjZTZkXHVkMmI4XHViOWFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVhYzcwXHVjNmI4XHViMzAwXHVjZTZkXHVkMmI4XHViOWFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzQwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHggJm5lOyB5LCAxICZsZTsgeCwgeSAmbGU7IE4pIHhcdWM2NDAgeVx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0XHVhY2UwLCB4XHVjNjQwIHlcdWFjMDAgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YjljZVx1YzU0NFx1YzU3YyBcdWQ1NThcdWIwOThcdWM3NTggXHVhYzA0XHVjMTIwXHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMyAmbGU7IE4sIE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YWM3MFx1YzZiOFx1YjMwMFx1Y2U2ZFx1ZDJiOFx1YjlhYyBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWJhNzQgWUVTXHViOTdjIFx1YzU0NFx1YjJjOFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDhcL3RyZWUuSlBHXCIgc3R5bGU9XCJoZWlnaHQ6MjcycHg7IHdpZHRoOjMyOHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVlIE1pcnJvcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IFQgYmUgYSByb290ZWQgdHJlZSAoYSBjb25uZWN0ZWQgdW5kaXJlY3RlZCBhY3lsaWMgZ3JhcGgpLCBhbmQgbGV0IFMgYmUgYSBwZXJmZWN0IGNvcHkgb2YgVC4gQ29uc3RydWN0IGEgbmV3IGdyYXBoIGJ5IHRha2luZyB0aGUgdW5pb24gb2YgVCBhbmQgUywgYW5kIG1lcmdpbmcgdGhlIGNvcnJlc3BvbmRpbmcgbGVhZiBub2RlcyAoYnV0IG5ldmVyIHRoZSByb290KS4gV2UgY2FsbCBzdWNoIGEgZ3JhcGggYSB0cmVlLW1pcnJvcmVkIGdyYXBoLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIGlmIGFuIGFyYml0cmFyeSB1bmRpcmVjdGVkIGNvbm5lY3RlZCBncmFwaCBpcyBhIHRyZWUtbWlycm9yZWQgZ3JhcGguPFwvcD5cclxuXHJcbjxwPnJtZmxhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0sIHRoZSBudW1iZXIgb2YgdmVydGljZXMgYW5kIGVkZ2VzIG9mIGEgZ3JhcGggRy4gVGhlIHZlcnRpY2VzIGluIEcgYXJlIGxhYmVsZWQgZnJvbSAxIHRvIE4uIFRoZSBmb2xsb3dpbmcgTSBsaW5lcyBkZXNjcmliZSB0aGUgZWRnZXMuIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4IGFuZCB5ICh4ICZuZTsgeTsgMSAmbGU7IHgsIHkgJmxlOyBOKSwgZGVzY3JpYmluZyBvbmUgZWRnZS4gVGhlcmUgd2lsbCBiZSBhdCBtb3N0IG9uZSBlZGdlIGJldHdlZW4gYW55IHBhaXIgb2YgdmVydGljZXMuJm5ic3A7KDMgJmxlOyBOLCBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBzdHJpbmcgWUVTIGlmIHRoZSBncmFwaCBHIGlzIGEgdHJlZS1taXJyb3JlZCBncmFwaCwgYW5kIE5PIG90aGVyd2lzZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwOFwvdHJlZS5KUEdcIiBzdHlsZT1cImhlaWdodDoyNzJweDsgb3BhY2l0eTowLjk7IHdpZHRoOjMyOHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 8번