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

문제

상근이는 개인이 소유한 한 중소기업의 CEO이다. 이 회사의 소유주는 자신의 아들 정인이를 회사의 팀장으로 임명했다. 상근이는 정인이가 일을 잘하면 소유주가 CEO자리를 정인이에게 줄 것이라고 생각한다. 다행히 그는 정인이의 팀에 속하는 사람을 정할 수 있다. 따라서 상근이는 정인이를 위해 최대한 일을 못하는 팀을 만들려고 한다.

상근이는 같은 팀에 속했을 때, 일을 못하는 사람들의 쌍을 모두 알고 있다. 상근이는 팀의 난이도라는 말을 주로 사용하는데, 이것은 같은 팀에 속했을 때, 일을 못하는 쌍의 수를 팀원의 수로 나눈 값이다. 팀의 난이도가 높아질수록 팀을 관리하는 것은 매우 어렵다.

팀의 난이도가 가장 높은 그룹을 찾는 프로그램을 작성하시오.

위와 같은 경우에 난이도가 가장 높은 팀은 1, 2, 4, 5로 구성된 팀이다. 총 5개의 쌍이 일을 못하는 사람의 쌍이고, 이를 팀원의 수로 나누면 5/4가 된다. 예를 들어, 이 팀에 3을 추가하면, 난이도는 6/5로 감소하게 된다.

입력

입력의 첫째 줄에는 직원의 수 n과 같은 팀에 속하면 일을 못하는 쌍의 수 m이 주어진다. (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000)

다음 m개 줄에는 쌍에 속하는 두 사람의 번호 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ n, ai ≠ bi) 같은 쌍이 두 번 주어지는 경우는 없다.

출력

첫째 줄에는 가장 난이도가 높은 팀에 속하는 사람의 수 k (1 ≤ k ≤ n)를 출력한다. 그 다음 k개 줄에는 팀에 속하는 사람의 번호를 오름차순으로 출력한다. 난이도가 가장 높은 팀이 여럿인 경우에는 아무거나 출력한다.

예제 입력 1

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

예제 출력 1

4
1
2
4
5
W3sicHJvYmxlbV9pZCI6IjM2MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMDBcdWM3NTggXHViMDljXHVjNzc0XHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzFjXHVjNzc4XHVjNzc0IFx1YzE4Y1x1YzcyMFx1ZDU1YyBcdWQ1NWMgXHVjOTExXHVjMThjXHVhZTMwXHVjNWM1XHVjNzU4IENFT1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWMxOGNcdWM3MjBcdWM4ZmNcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzU0NFx1YjRlNCBcdWM4MTVcdWM3NzhcdWM3NzRcdWI5N2MgXHVkNjhjXHVjMGFjXHVjNzU4IFx1ZDMwMFx1YzdhNVx1YzczY1x1Yjg1YyBcdWM3ODRcdWJhODVcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjNzdjXHVjNzQ0IFx1Yzc5OFx1ZDU1OFx1YmE3NCBcdWMxOGNcdWM3MjBcdWM4ZmNcdWFjMDAgQ0VPXHVjNzkwXHViOWFjXHViOTdjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5MDQgXHVhYzgzXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVkNTg5XHVkNzg4IFx1YWRmOFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHVkMzAwXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODE1XHVjNzc4XHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjNzdjXHVjNzQ0IFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzdjXHVjNzQ0IFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVjMzBkXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkMzAwXHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1Yjc3Y1x1YjI5NCBcdWI5ZDBcdWM3NDQgXHVjOGZjXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVjNzc0XHVhYzgzXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzdjXHVjNzQ0IFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjMjE4XHViOTdjIFx1ZDMwMFx1YzZkMFx1Yzc1OCBcdWMyMThcdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMlx1Yzc3NFx1YjJlNC4gXHVkMzAwXHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YWMwMCBcdWIxOTJcdWM1NDRcdWM5YzhcdWMyMThcdWI4NWQgXHVkMzAwXHVjNzQ0IFx1YWQwMFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzViNFx1YjgzNVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMzAwXHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YWRmOFx1YjhmOVx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oYXJkdGVhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTRweDsgd2lkdGg6MTU1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVkMzAwXHVjNzQwIDEsIDIsIDQsIDVcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1ZDMwMFx1Yzc3NFx1YjJlNC4gXHVjZDFkIDVcdWFjMWNcdWM3NTggXHVjMzBkXHVjNzc0IFx1Yzc3Y1x1Yzc0NCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzMwZFx1Yzc3NFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1ZDMwMFx1YzZkMFx1Yzc1OCBcdWMyMThcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0IDVcLzRcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3NzQgXHVkMzAwXHVjNWQwIDNcdWM3NDQgXHVjZDk0XHVhYzAwXHVkNTU4XHViYTc0LCBcdWIwOWNcdWM3NzRcdWIzYzRcdWIyOTQgNlwvNVx1Yjg1YyBcdWFjMTBcdWMxOGNcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjNmQwXHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTU4XHViYTc0IFx1Yzc3Y1x1Yzc0NCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjMzBkXHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwLCAwICZsZTsgbSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMzMGRcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4IGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyBuLCBhPHN1Yj5pPFwvc3ViPiAmbmU7IGI8c3ViPmk8XC9zdWI+KSBcdWFjMTlcdWM3NDAgXHVjMzBkXHVjNzc0IFx1YjQ1MCBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggayAoMSAmbGU7IGsmbmJzcDsmbGU7IG4pXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBrXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVkMzAwXHVjNzc0IFx1YzVlY1x1YjdmZlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNjExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFyZCBMaWZlIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huIGlzIGEgQ2hpZWYgRXhlY3V0aXZlIE9cdWZiMDNjZXIgYXQgYSBwcml2YXRlbHkgb3duZWQgbWVkaXVtIHNpemUgY29tcGFueS4gVGhlIG93bmVyIG9mIHRoZSBjb21wYW55IGhhcyBkZWNpZGVkIHRvIG1ha2UgaGlzIHNvbiBTY290dCBhIG1hbmFnZXIgaW4gdGhlIGNvbXBhbnkuIEpvaG4gZmVhcnMgdGhhdCB0aGUgb3duZXIgd2lsbCB1bHRpbWF0ZWx5IGdpdmUgQ0VPIHBvc2l0aW9uIHRvIFNjb3R0IGlmIGhlIGRvZXMgd2VsbCBvbiBoaXMgbmV3IG1hbmFnZXIgcG9zaXRpb24sIHNvIGhlIGRlY2lkZWQgdG8gbWFrZSBTY290dCZyc3F1bztzIGxpZmUgYXMgaGFyZCBhcyBwb3NzaWJsZSBieSBjYXJlZnVsbHkgc2VsZWN0aW5nIHRoZSB0ZWFtIGhlIGlzIGdvaW5nIHRvIG1hbmFnZSBpbiB0aGUgY29tcGFueS48XC9wPlxyXG5cclxuPHA+Sm9obiBrbm93cyB3aGljaCBwYWlycyBvZiBoaXMgcGVvcGxlIHdvcmsgcG9vcmx5IGluIHRoZSBzYW1lIHRlYW0uIEpvaG4gaW50cm9kdWNlZCBhIGhhcmRuZXNzIGZhY3RvciBvZiBhIHRlYW0gJm1kYXNoOyBpdCBpcyBhIG51bWJlciBvZiBwYWlycyBvZiBwZW9wbGUgZnJvbSB0aGlzIHRlYW0gd2hvIHdvcmsgcG9vcmx5IGluIHRoZSBzYW1lIHRlYW0gZGl2aWRlZCBieSB0aGUgdG90YWwgbnVtYmVyIG9mIHBlb3BsZSBpbiB0aGUgdGVhbS4gVGhlIGxhcmdlciBpcyB0aGUgaGFyZG5lc3MgZmFjdG9yLCB0aGUgaGFyZGVyIGlzIHRoaXMgdGVhbSB0byBtYW5hZ2UuIEpvaG4gd2FudHMgdG8gXHVmYjAxbmQgYSBncm91cCBvZiBwZW9wbGUgaW4gdGhlIGNvbXBhbnkgdGhhdCBhcmUgaGFyZGVyc3QgdG8gbWFuYWdlIGFuZCBtYWtlIGl0IFNjb3R0JnJzcXVvO3MgdGVhbS4gUGxlYXNlLCBoZWxwIGhpbS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oYXJkdGVhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTRweDsgd2lkdGg6MTU1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGV4YW1wbGUgb24gdGhlIHBpY3R1cmUgdGhlIGhhcmRlc3QgdGVhbSBjb25zaXN0cyBvZiBwZW9wbGUgMSwgMiwgNCwgYW5kIDUuIEFtb25nIDQgb2YgdGhlbSA1IHBhaXJzIHdvcmsgcG9vcmx5IGluIHRoZSBzYW1lIHRlYW0sIHRodXMgaGFyZG5lc3MgZmFjdG9yIGlzIGVxdWFsIHRvIDVcLzQuIElmIHdlIGFkZCBwZXJzb24gbnVtYmVyIDMgdG8gdGhlIHRlYW0gdGhlbiBoYXJkbmVzcyBmYWN0b3IgZGVjcmVhc2VzIHRvIDZcLzUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgbiBhbmQgbSAoMSAmbGU7IG4gJmxlOyAxMDAsIDAgJmxlOyBtICZsZTsgMTAwMCkuIEhlcmUgbiBpcyBhIHRvdGFsIG51bWJlciBvZiBwZW9wbGUgaW4gdGhlIGNvbXBhbnkgKHBlb3BsZSBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4pLCBhbmQgbSBpcyB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIHBlb3BsZSB3aG8gd29yayBwb29ybHkgaW4gdGhlIHNhbWUgdGVhbS4gTmV4dCBtIGxpbmVzIGRlc2NyaWJlIHRob3NlIHBhaXJzIHdpdGggdHdvIGludGVnZXIgbnVtYmVycyBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4mbmJzcDsoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgbiwgYTxzdWI+aTxcL3N1Yj4mbmJzcDsmbmU7IGI8c3ViPmk8XC9zdWI+KSBvbiBhIGxpbmUuIFRoZSBvcmRlciBvZiBwZW9wbGUgaW4gYSBwYWlyIGlzIGFyYml0cmFyeSBhbmQgbm8gcGFpciBpcyBsaXN0ZWQgdHdpY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdG8gdGhlIG91dHB1dCBcdWZiMDFsZSBhbiBpbnRlZ2VyIG51bWJlciBrICgxICZsZTsgayAmbGU7IG4pICZtZGFzaDsgdGhlIG51bWJlciBvZiBwZW9wbGUgaW4gdGhlIGhhcmRlc3QgdGVhbSwmbmJzcDtmb2xsb3dlZCBieSBrIGxpbmVzIGxpc3RpbmcgcGVvcGxlIGZyb20gdGhpcyB0ZWFtIGluIGFzY2VuZGluZyBvcmRlci4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHRlYW1zIHdpdGggdGhlJm5ic3A7c2FtZSBoYXJkbmVzcyBmYWN0b3IgdGhlbiB3cml0ZSBhbnkgb25lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2006 H번