시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 92 28 21 29.167%

문제

정보를 좋아하는 고등학생 민솔이는 커플을 싫어한다. 그런데 요즘 주변에서 커플이 많이 출몰하는 것을 본 민솔이는 마음이 많이 심란하다. 민솔이는 이 문제를 해결하기 위해 정보를 매우 잘하는 '갓' 승원이를 찾아갔다.

승원이는 잠시 생각해 본 후, 학교의 모든 사람에 대해 그 사람이 좋아하는 사람의 수와 그 사람을 좋아하는 사람의 수의 차가 1 이하가 된다면 모든 커플을 깨트릴 수 있다는 것을 알아내었다. 다시 말해, 각 사람을 그래프의 노드로 보고, 'A가 B를 좋아한다'라는 것을 A에서 B를 가리키는 방향성 간선(즉, A -> B)으로 생각했을 때, 각 노드에 대해 |(그 노드로 들어오는 간선의 수) - (그 노드에서 나가는 간선의 수)|가 1 이하가 되면 된다는 것이다.

승원이는 '갓'이기 때문에, 학교 내에서 서로 알고 있는 학생의 쌍의 정보에 대해 모두 알고 있다. 그리고 승원이는 임의의 서로 아는 두 학생 A, B에 대해, A가 B를 좋아하거나, B가 A를 좋아하게 만들 수 있다. 즉, 어떤 무방향성 그래프가 주어지면, 승원이는 어떤 (s, e)를 잇는 간선에 대해 s -> e 또는 e -> s의 방향성 간선을 만들 수 있다는 것이다.

민솔이가 위의 조건을 만족하는 간선 방향 조합을 어떻게 생성하면 되는지 물어보려는 순간, 승원이는 "난 Persistent Segment Tree를 짜러 가야 해서... 그럼 이만!" 이라는 이상한 말과 함께 학생들 간의 관계 정보만을 남기고 떠나가버렸다.

어찌할 지 몰라 잉잉 울고 있는 민솔이를 도와 커플을 깨트릴 수 있는 간선 방향 조합을 찾아 승원이에게 알려주자!

입력

첫째 줄에는 공백으로 구분된 정수 N과 M이 주어진다(1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000). N은 학생의 수, M은 두 학생이 서로 아는 관계의 수를 나타낸다.

다음 M개의 줄에는 각 줄별로 공백으로 구분된 정수 A, B가 주어진다(1 ≤ A, B ≤ N). 이는 A번 학생과 B번 학생이 서로 알고 있음을 나타낸다. (A, B)의 쌍은 중복해서 들어오지 않는다.

출력

만약 문제의 조건을 만족하도록 각 간선의 방향을 설정하는 것이 가능하다면 첫 번째 줄에 "Yes"를 출력하고, (따옴표 제외) 이후의 M개 줄에 각각 정수 A, B를 출력한다. 이는 A가 B를 좋아한다(즉, A -> B로 방향을 설정했다)라는 의미이다. 조건을 만족하도록 간선의 방향을 설정하는 방법이 여러 가지라면 그 중 아무 방법이나 출력하면 된다.

만약 문제의 조건을 만족하도록 간선의 방향을 설정하는 것이 불가능하면 첫 번째 줄에 "No"를 출력한다. (따옴표 제외)

예제 입력 1

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

예제 출력 1

Yes
1 2
3 1
4 1
1 5
2 3
5 4
3 5

힌트

예제에서는 5명의 학생과 7개의 서로 아는 관계가 있다. 예제 출력과 같이 간선 방향을 설정하고 나면, 1, 2, 4번 학생은 자신이 좋아하는 학생 수와 자신을 좋아하는 학생 수가 같으며, 3번 학생은 자신이 좋아하는 학생 수가 자신을 좋아하는 학생 수보다 1 많으며, 5번 학생은 자신을 좋아하는 학생 수가 자신이 좋아하는 학생 수보다 1 많게 되어 문제의 조건을 만족한다.

W3sicHJvYmxlbV9pZCI6IjMyMDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZTRcdWQ1MGMgXHVhZTY4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWJjZjRcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YWNlMFx1YjRmMVx1ZDU1OVx1YzBkZCBcdWJiZmNcdWMxOTRcdWM3NzRcdWIyOTQgXHVjZWU0XHVkNTBjXHVjNzQ0IFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YzY5NFx1Yzk5OCBcdWM4ZmNcdWJjYzBcdWM1ZDBcdWMxMWMgXHVjZWU0XHVkNTBjXHVjNzc0IFx1YjljZVx1Yzc3NCBcdWNkOWNcdWJhYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmNmOCBcdWJiZmNcdWMxOTRcdWM3NzRcdWIyOTQgXHViOWM4XHVjNzRjXHVjNzc0IFx1YjljZVx1Yzc3NCBcdWMyZWNcdWI3ODBcdWQ1NThcdWIyZTQuIFx1YmJmY1x1YzE5NFx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODE1XHViY2Y0XHViOTdjIFx1YjllNFx1YzZiMCBcdWM3OThcdWQ1NThcdWIyOTQgJiMzOTtcdWFjMTMmIzM5OyBcdWMyYjlcdWM2ZDBcdWM3NzRcdWI5N2MgXHVjYzNlXHVjNTQ0XHVhYzE0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjN2EwXHVjMmRjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjggXHVkNmM0LCBcdWQ1NTlcdWFkNTBcdWM3NTggXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNzU4IFx1Y2MyOFx1YWMwMCAxIFx1Yzc3NFx1ZDU1OFx1YWMwMCBcdWI0MWNcdWIyZTRcdWJhNzQgXHViYWE4XHViNGUwIFx1Y2VlNFx1ZDUwY1x1Yzc0NCBcdWFlNjhcdWQyYjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVjNWM4XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0LCBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHViY2Y0XHVhY2UwLCAmIzM5O0FcdWFjMDAgQlx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQmIzM5O1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgQVx1YzVkMFx1YzExYyBCXHViOTdjIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhYzA0XHVjMTIwKFx1Yzk4OSwgQSAtJmd0OyBCKVx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHViMTc4XHViNGRjXHVjNWQwIFx1YjMwMFx1ZDU3NCA8c3Ryb25nPnwoXHVhZGY4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOCkgLSAoXHVhZGY4IFx1YjE3OFx1YjRkY1x1YzVkMFx1YzExYyBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOCl8XHVhYzAwIDEgXHVjNzc0XHVkNTU4PFwvc3Ryb25nPlx1YWMwMCBcdWI0MThcdWJhNzQgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0ICYjMzk7XHVhYzEzJiMzOTtcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NTlcdWFkNTAgXHViMGI0XHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMzMGRcdWM3NTggXHVjODE1XHViY2Y0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWJhYThcdWI0NTAgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVjMTFjXHViODVjIFx1YzU0NFx1YjI5NCBcdWI0NTAgXHVkNTU5XHVjMGRkIEEsIEJcdWM1ZDAgXHViMzAwXHVkNTc0LCBBXHVhYzAwIEJcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhYzcwXHViMDk4LCBCXHVhYzAwIEFcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhYzhjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YzViNFx1YjVhNCBcdWJiMzRcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YzViNFx1YjVhNCAocywgZSlcdWI5N2MgXHVjNzg3XHViMjk0IFx1YWMwNFx1YzEyMFx1YzVkMCBcdWIzMDBcdWQ1NzQgcyAtJmd0OyBlIFx1YjYxMFx1YjI5NCBlIC0mZ3Q7IHNcdWM3NTggXHViYzI5XHVkNWE1XHVjMTMxIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmJmY1x1YzE5NFx1Yzc3NFx1YWMwMCBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjAgXHViYzI5XHVkNWE1IFx1Yzg3MFx1ZDU2OVx1Yzc0NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjMGRkXHVjMTMxXHVkNTU4XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWJiM2NcdWM1YjRcdWJjZjRcdWI4MjRcdWIyOTQgXHVjMjFjXHVhYzA0LCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgJnF1b3Q7XHViMDljIFBlcnNpc3RlbnQgU2VnbWVudCBUcmVlXHViOTdjIFx1YzlkY1x1YjdlYyBcdWFjMDBcdWM1N2MgXHVkNTc0XHVjMTFjLi4uIFx1YWRmOFx1YjdmYyBcdWM3NzRcdWI5Y2MhJnF1b3Q7IFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWM3NzRcdWMwYzFcdWQ1NWMgXHViOWQwXHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWQ1NTlcdWMwZGRcdWI0ZTQgXHVhYzA0XHVjNzU4IFx1YWQwMFx1YWNjNCBcdWM4MTVcdWJjZjRcdWI5Y2NcdWM3NDQgXHViMGE4XHVhZTMwXHVhY2UwIFx1YjVhMFx1YjA5OFx1YWMwMFx1YmM4NFx1YjgzOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHVjYzBjXHVkNTYwIFx1YzljMCBcdWJhYjBcdWI3N2MgXHVjNzg5XHVjNzg5IFx1YzZiOFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYmZjXHVjMTk0XHVjNzc0XHViOTdjIFx1YjNjNFx1YzY0MCBcdWNlZTRcdWQ1MGNcdWM3NDQgXHVhZTY4XHVkMmI4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzA0XHVjMTIwIFx1YmMyOVx1ZDVhNSBcdWM4NzBcdWQ1NjlcdWM3NDQgXHVjYzNlXHVjNTQ0IFx1YzJiOVx1YzZkMFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM1NGNcdWI4MjRcdWM4ZmNcdWM3OTAhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHVjODE1XHVjMjE4IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMSAmbGU7IE4gJmxlOyAxMDAwLCAxICZsZTsgTSAmbGU7IDEwMDAwMCkuIE5cdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCwgTVx1Yzc0MCBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM1NDRcdWIyOTQgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjOTA0XHViY2M0XHViODVjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHVjODE1XHVjMjE4IEEsIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDEgJmxlOyBBLCBCICZsZTsgTikuIFx1Yzc3NFx1YjI5NCBBXHViYzg4IFx1ZDU1OVx1YzBkZFx1YWNmYyBCXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIChBLCBCKVx1Yzc1OCBcdWMzMGRcdWM3NDAgXHVjOTExXHViY2Y1XHVkNTc0XHVjMTFjIFx1YjRlNFx1YzViNFx1YzYyNFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHVjNTdkIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM3NTggXHViYzI5XHVkNWE1XHVjNzQ0IFx1YzEyNFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICZxdW90O1llcyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIChcdWI1MzBcdWM2MzRcdWQ0NWMgXHVjODFjXHVjNjc4KSBcdWM3NzRcdWQ2YzRcdWM3NTggTVx1YWMxYyBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIFx1YzgxNVx1YzIxOCBBLCBCXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViMjk0IEFcdWFjMDAgQlx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQoXHVjOTg5LCBBIC0mZ3Q7IEJcdWI4NWMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YzEyNFx1YzgxNVx1ZDU4OFx1YjJlNClcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjMTI0XHVjODE1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0IFx1YWRmOCBcdWM5MTEgXHVjNTQ0XHViYjM0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWMxMjRcdWM4MTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAmcXVvdDtObyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWI1MzBcdWM2MzRcdWQ0NWMgXHVjODFjXHVjNjc4KTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgNVx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWFjZmMgN1x1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHVjNTQ0XHViMjk0IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWMwNFx1YzEyMCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjMTI0XHVjODE1XHVkNTU4XHVhY2UwIFx1YjA5OFx1YmE3NCwgMSwgMiwgNFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHVjNjQwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkIFx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzAsIDNcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkIFx1YzIxOFx1YWMwMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZCBcdWMyMThcdWJjZjRcdWIyZTQgMSBcdWI5Y2VcdWM3M2NcdWJhNzAsIDVcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkIFx1YzIxOFx1YWMwMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZCBcdWMyMThcdWJjZjRcdWIyZTQgMSBcdWI5Y2VcdWFjOGMgXHViNDE4XHVjNWI0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzIwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikxpa2UiLCJkZXNjcmlwdGlvbiI6IjxwPkhhdmUgeW91IG5vdGljZWQsIHRoYXQgaWYgd2UgcmVtb3ZlIHRoZSBsZXR0ZXIgJmxzcXVvO2smcnNxdW87IGZyb20gdGhlIHdvcmQgJmxkcXVvO2xpa2UmcmRxdW87IGFuZCBtYWtlIGFsbCBjeWNsaWMgcm90YXRpb25zLCBvbmUgb2YgdGhlbSB3aWxsIGJlICZsZHF1bztlbGkmcmRxdW87PyBUaGlzIGNvdWxkIGJlY29tZSBhIGdyZWF0IHRhc2ssIGhvd2V2ZXIgaW4gdGhpcyBvbmUgeW91IHdpbGwgZGVhbCBuZWl0aGVyIHdpdGggd29yZHMsIG5vciB3aXRoIGN5Y2xpYyByb3RhdGlvbnMuPFwvcD5cclxuXHJcbjxwPkVsbHkgaXMgZmFjaW5nIGEgYmlnIHByb2JsZW0uIFJlY2VudGx5IHNoZSB3YXMgYWNjdXNlZCAobm90IHdpdGhvdXQgYSByZWFzb24pIHRoYXQgYWxsIGJveXMgaW4gaGVyIGNsYXNzIGxpa2UgaGVyICh3aGlsZSBub3QgcGF5aW5nIGFueSBhdHRlbnRpb24gdG8gdGhlIG90aGVyIGdpcmxzKSwgYW5kIHNoZSwgb24gdGhlIG90aGVyIGhhbmQsIGlzIG5vdCBwYXlpbmcgYW55IGF0dGVudGlvbiB0byB0aGUgYm95cy4gVGhpcyBhY2N1c2F0aW9uIHdhcyBtYWRlIG1vc3RseSBiZWNhdXNlIHNvbWUgb2YgaGVyIHNjaG9vbG1hdGVzIHdlcmUgamVhbG91cyB0aGF0IHNoZSBpcyBtdWNoIG1vcmUgbGlrZWQgdGhhbiBzaGUgbGlrZXMgdGhlIG90aGVycy4gRWxseSwgb24gdGhlIG90aGVyIGhhbmQsIGlzIGFnYWluc3QgcmVsYXRpb25zaGlwcyAmbmRhc2g7IHRoYXQgaXMgYWxzbyB0aGUgcmVhc29uIHdoeSBzaGUgaWdub3JlcyB0aGUgYm95cyBpbiBoZXIgY2xhc3MuIFNvbWV0aGluZyBtb3JlICZuZGFzaDsgc2hlIHdvdWxkIGJlIGhhcHB5IGlmIHRoZXJlIGFyZSBhcyBmZXcgYXMgcG9zc2libGUgY291cGxlcyBhcm91bmQgaGVyLjxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBhdm9pZCBmdXR1cmUgY29uZmxpY3RzLCBzaGUgZGVjaWRlZCB0byBtYWtlIHN1cmUgdGhhdCBmb3IgZXZlcnkgcGVyc29uIGluIHRoZSBzY2hvb2wgdGhlIGZvbGxvd2luZyBob2xkczogdGhlIG51bWJlciBvZiBwZW9wbGUgaGUgbGlrZXMgZGlmZmVycyBmcm9tIHRoZSBudW1iZXIgb2YgcGVvcGxlIHRoYXQgbGlrZSBoaW0gYnkgbm8gbW9yZSB0aGFuIDEuIFB1dCBpbiBhIG1vcmUgaHVtYW4gbGFuZ3VhZ2UsIGlmIHdlIGltYWdpbmUgdGhhdCBlYWNoIHBlcnNvbiBpcyBhIG5vZGUgaW4gYSBncmFwaCBhbmQgdGhlIGZhY3QgdGhhdCBBIGxpa2VzIEIgYXMgZGlyZWN0ZWQgZWRnZSBmcm9tIEEgdG8gQiBpbiB0aGUgZ3JhcGgsIHRoZW4gc2hlIHdhbnRzIHRoZSBudW1iZXIgb2YgaW5jb21pbmcgZWRnZXMgdG8gZGlmZmVyIGZyb20gdGhlIG51bWJlciBvZiBvdXRnb2luZyBlZGdlcyBieSBubyBtb3JlIHRoYW4gMS48XC9wPlxyXG5cclxuPHA+U2hlIGhhcyBkZWNpZGVkIHRvIHVzZSBoZXIgY2hhcm0gYW5kIGRpcGxvbWFjeSAoYWxzbyBrbm93biBhcyBkZWNlaXQgYW5kIG1hbmlwdWxhdGlvbikgaW4gb3JkZXIgdG8gYWNoaWV2ZSB0aGlzLiBFbGxlb25vcmEga25vd3MgYWxsIHBhaXJzIG9mIHBlb3BsZSBpbiB0aGUgc2Nob29sIHRoYXQga25vdyBlYWNoLW90aGVyICh3aGljaCB3ZSBjYW4gYXNzdW1lIGlzIGFuIHVuZGlyZWN0ZWQgZWRnZSBpbiB0aGUgZ3JhcGgpLiBTaGUgY2FuIG1ha2UgYW55IHBhaXIgb2YgYWNxdWFpbnRhbmNlcyBjaGFuZ2UgdGhlaXIgcmVsYXRpb25zaGlwLCBzbyB0aGF0IG9uZSBvZiB0aGVtIHN0YXJ0cyBsaWtpbmcgdGhlIG90aGVyIG9yIHZpY2V2ZXJzYSwgYnV0IG5vdCBib3RoIGF0IHRoZSBzYW1lIHRpbWUgKGRvbiZyc3F1bzt0IGZvcmdldCB0aGF0IHNoZSBpcyBhZ2FpbnN0IGhhdmluZyBjb3VwbGVzIGluIHRoZSBzY2hvb2wpLiBTaGUgd2FudHMgdG8gZXhlY3V0ZSBoZXIgZXZpbCBwbGFuIGJ5ICZsZHF1bztkaXJlY3RpbmcmcmRxdW87IGFsbCBlZGdlcyBpbiB0aGUgZ3JhcGggJm5kYXNoOyBpLmUuIGVhY2ggYWNxdWFpbnRhbmNlc2hpcCB0byBiZWNvbWUgYSBvbmUtd2F5IGNydXNoLjxcL3A+XHJcblxyXG48cD5Zb3UgZGVjaWRlIHRvIGNoZWNrIGlmIHNoZSBjYW4gZG8gdGhhdCAmbmRhc2g7IGFuZCBpZiBzaGUgY2FuIHRvIHNob3cgb25lIG9mIHRoZSBwb3NzaWJsZSBkaXJlY3Rpb25zIG9mIHRoZSBlZGdlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB3aWxsIGJlIGdpdmVuIHR3byBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMgTiBhbmQgTSAmbmRhc2g7IHRoZSBudW1iZXIgb2YgcGVvcGxlIGluIHRoZSBzY2hvb2wgYW5kIHRoZSBudW1iZXIgb2YgYWNxdWFpbnRhbmNlcywgcmVzcGVjdGl2ZWx5LiBPbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyB3aWxsIGJlIGdpdmVuIGEgcGFpciBvZiBzcGFjZSBzZXBhcmF0ZWQgbnVtYmVycyBQPHN1Yj4xPFwvc3ViPiBhbmQgUDxzdWI+MjxcL3N1Yj4sIHdoZXJlIDEgJmxlOyBQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4gJmxlOyBOLCBtZWFuaW5nIHRoYXQgdGhlIHN0dWRlbnRzIFA8c3ViPjE8XC9zdWI+IGFuZCBQPHN1Yj4yPFwvc3ViPiBrbm93IGVhY2gtb3RoZXIuIEVhY2ggYWNxdWFpbnRhbmNlIHdpbGwgYmUgZ2l2ZW4gZXhhY3RseSBvbmNlIGluIHRoZSBpbnB1dC4gQWxsIG51bWJlcnMgaW4gdGhlIGlucHV0IHdpbGwgYmUgcG9zaXRpdmUgaW50ZWdlcnMuICgxICZsZTsgTiAmbGU7IDEwMDAsIDEgJmxlOyBNICZsZTsgMTAwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgcHJpbnQgJmxkcXVvO1llcyZyZHF1bzsgaWYgc3VjaCBkaXJlY3Rpb24gb2YgdGhlIGVkZ2VzIGlzIHBvc3NpYmxlLCBvciAmbGRxdW87Tm8mcmRxdW87IG90aGVyd2lzZSAocXVvdGVzIGZvciBjbGFyaXR5IG9ubHkpLiBJZiB0aGUgYW5zd2VyIGlzICZsZHF1bztZZXMmcmRxdW87IG9uIGVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBwcmludCBhIHBhaXIgb2Ygc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzIFA8c3ViPjE8XC9zdWI+IFA8c3ViPjI8XC9zdWI+LCBtZWFuaW5nIHRoYXQgUDxzdWI+MTxcL3N1Yj4gbGlrZXMgUDxzdWI+MjxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGV4aXN0IG1vcmUgdGhhbiBvbmUgc3VjaCB3YXkgdG8gZGlyZWN0IHRoZSBlZGdlcywgcHJpbnQgYW55IG9mIHRoZW0uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZXJlIGFyZSA1IHN0dWRlbnRzIGFuZCA3IGFjcXVhaW50YW5jZXMgYmV0d2VlbiB0aGVtLiBBZnRlciBkaXJlY3RpbmcgdGhlIGVkZ2VzIGluIHRoZSBncmFwaCwgZWFjaCBzdHVkZW50IGlzIGxpa2VkIGJ5IGFuZCBsaWtlcyBlcXVhbCBhbW91bnQgb2YgcGVvcGxlLCBleGNlcHQgNSwgd2hvIGlzIGxpa2VkIGJ5IG9uZSBtb3JlIHBlcnNvbiwgYW5kIDMsIHdobyBsaWtlcyBvbmUgbW9yZSBwZXJzb24uJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Tournament in Informatics > Shumen 2010 A1번

  • 문제를 번역한 사람: kdh9949