시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 129 29 28 48.276%

문제

학생들이 너무 떠드는 것을 보다 못한 나머지, 원장님은 결단을 내리셨다. 반을 나누기로.

학생들은 친한 친구들과 떨어지는 것이 싫어서 몹시 거세게 반발했고, 원장님은 이를 잠재우기 위하여 한 가지 방안을 제시하셨다. 인터넷 메신저로 대화할 수 있게 허락해 주신 것이다.

단, 두 사람이 메신저로 대화를 나누기 위해서는 서로가 서로의 메신저 아이디를 알고 있어야 하는데, 모든 학생이 모든 학생의 아이디를 알고 있는 것은 아니다.

이러한 상황에서, 원장님은 최대한 반을 잘게 나누고자 하신다. 다른 반에 속한 학생들끼리는 메신저로 대화해야 하므로, 반드시 서로의 메신저 아이디를 알고 있어야만 한다.

어떤 학생들끼리 서로의 메신저 아이디를 알고 있는지 주어졌을 때, 가장 많은 반을 편성하려면 어떻게 해야 하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄 학생들의 수 n과, 서로 메신저 아이디를 알고 있는 학생들 쌍의 수 m이 공백을 사이에 두고 주어진다. (2<=n<=100,000. 1<=m<=2,000,000) 이후 m개의 줄에는 서로 메신저 아이디를 알고 있는 학생들 번호의 쌍이 두 개의 정수로 주어진다. 두 학생의 번호는 1이상 n이하의 정수이다.

출력

첫째 줄에, 최대로 편성할 수 있는 반이 몇 개인지 출력한다. 둘째 줄에는, 최대로 편성했을 때 각 반별 인원수를 오름차순으로 출력한다.

예제 입력 1

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

예제 출력 1

3
1 2 4

힌트

4번 학생 혼자 한 반, 5번과 7번 학생 둘이서 한 반, 나머지 학생 네 명이서 한 반이 되도록 반을 편성하면 된다.

W3sicHJvYmxlbV9pZCI6IjE3NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTggXHViMDk4XHViMjA0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHViMTA4XHViYjM0IFx1YjVhMFx1YjRkY1x1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHViMmU0IFx1YmFiYlx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAsIFx1YzZkMFx1YzdhNVx1YjJkOFx1Yzc0MCBcdWFjYjBcdWIyZThcdWM3NDQgXHViMGI0XHViOWFjXHVjMTY4XHViMmU0LiBcdWJjMThcdWM3NDQgXHViMDk4XHViMjA0XHVhZTMwXHViODVjLjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjZTVjXHVkNTVjIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzJlYlx1YzViNFx1YzExYyBcdWJhYjlcdWMyZGMgXHVhYzcwXHVjMTM4XHVhYzhjIFx1YmMxOFx1YmMxY1x1ZDU4OFx1YWNlMCwgXHVjNmQwXHVjN2E1XHViMmQ4XHVjNzQwIFx1Yzc3NFx1Yjk3YyBcdWM3YTBcdWM3YWNcdWM2YjBcdWFlMzAgXHVjNzA0XHVkNTU4XHVjNWVjIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYzI5XHVjNTQ4XHVjNzQ0IFx1YzgxY1x1YzJkY1x1ZDU1OFx1YzE2OFx1YjJlNC4gXHVjNzc4XHVkMTMwXHViMTM3IFx1YmE1NFx1YzJlMFx1YzgwMFx1Yjg1YyBcdWIzMDBcdWQ2NTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWQ1YzhcdWI3N2RcdWQ1NzQgXHVjOGZjXHVjMmUwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4LCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YmE1NFx1YzJlMFx1YzgwMFx1Yjg1YyBcdWIzMDBcdWQ2NTRcdWI5N2MgXHViMDk4XHViMjA0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWMxMWNcdWI4NWNcdWFjMDAgXHVjMTFjXHViODVjXHVjNzU4IFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjLCBcdWM2ZDBcdWM3YTVcdWIyZDhcdWM3NDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmMxOFx1Yzc0NCBcdWM3OThcdWFjOGMgXHViMDk4XHViMjA0XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YzJlMFx1YjJlNC4gXHViMmU0XHViOTc4IFx1YmMxOFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHViMDdjXHViOWFjXHViMjk0IFx1YmE1NFx1YzJlMFx1YzgwMFx1Yjg1YyBcdWIzMDBcdWQ2NTRcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjLCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjMTFjXHViODVjXHVjNzU4IFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWIwN2NcdWI5YWMgXHVjMTFjXHViODVjXHVjNzU4IFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmMxOFx1Yzc0NCBcdWQzYjhcdWMxMzFcdWQ1NThcdWI4MjRcdWJhNzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMyMTggblx1YWNmYywgXHVjMTFjXHViODVjIFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTQgXHVjMzBkXHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDImbHQ7PW4mbHQ7PTEwMCwwMDAuIDEmbHQ7PW0mbHQ7PTIsMDAwLDAwMCkgXHVjNzc0XHVkNmM0IG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWJhNTRcdWMyZTBcdWM4MDAgXHVjNTQ0XHVjNzc0XHViNTE0XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0IFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWMzMGRcdWM3NzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHVjNzc0XHVjMGMxIG5cdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQzYjhcdWMxMzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMThcdWM3NzQgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQzYjhcdWMxMzFcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YWMwMSBcdWJjMThcdWJjYzQgXHVjNzc4XHVjNmQwXHVjMjE4XHViOTdjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjRcdWJjODggXHVkNTU5XHVjMGRkIFx1ZDYzY1x1Yzc5MCBcdWQ1NWMgXHViYzE4LCA1XHViYzg4XHVhY2ZjIDdcdWJjODggXHVkNTU5XHVjMGRkIFx1YjQ1OFx1Yzc3NFx1YzExYyBcdWQ1NWMgXHViYzE4LCBcdWIwOThcdWJhMzhcdWM5YzAgXHVkNTU5XHVjMGRkIFx1YjEyNCBcdWJhODVcdWM3NzRcdWMxMWMgXHVkNTVjIFx1YmMxOFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHViYzE4XHVjNzQ0IFx1ZDNiOFx1YzEzMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT2ZmaWNlcyIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZWwgaXMgYSBtb2JpbGUgdGVsZXBob255IHBvdGVudGF0ZS4gRWFjaCBlbXBsb3llZSBoYXMgYmVlbiBpc3N1ZWQgYSBjb21wYW55IHBob25lLCB0aGUgbWVtb3J5IG9mIHdoaWNoIGhvbGRzIHRoZSBudW1iZXJzIG9mIHNvbWUgb2YgaGlzIGNvLXdvcmtlcnMgKGFsbCBvZiB0aGVtIGhhdmUgaGlzIG51bWJlciBpbiB0aGVpciBwaG9uZXMgYXMgd2VsbCkuIER1ZSB0byBkeW5hbWljIGdyb3d0aCBvZiB0aGVpciBvcGVyYXRpb25zIHRoZSBib2FyZCBvZiBkaXJlY3RvcnMgaW50ZW5kcyB0byBtb3ZlIGNvbXBhbnkgaGVhZHF1YXRlcnMgdG8gbmV3IG9mZmljZSBidWlsZGluZ3MuIEl0IGhhcyBiZWVuIGRlY2lkZWQgLSBpbiBvcmRlciB0byBib29zdCB3b3JrIGVmZmljaWVuY3kgLSB0aGF0IGV2ZXJ5IHBhaXIgb2YgZW1wbG95ZWVzIHdvcmtpbmcgaW4gZGlmZmVyZW50IGJ1aWxkaW5ncyBzaG91bGQga25vdyAocmVjaXByb2NhbGx5KSBlYWNoIG90aGVycyBwaG9uZSBudW1iZXIgaS5lLiB0aGUgbWVtb3J5IG9mIHRoZWlyIGNvbXBhbnkgcGhvbmUgb3VnaHQgdG8gaG9sZCBuZWNlc3NhcnkgcGhvbmUgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+U2ltdWx0YW5lb3VzbHksIHRoZSBib2FyZCBoYXZlIGRlY2lkZWQgdG8gcmVudCBhcyBtYW55IG9mZmljZSBidWlsZGluZ3MgYXMgcG9zc2libGUgdG8gZW5zdXJlIGdvb2Qgd29ya2luZyBjb25kaXRpb25zLiBIZWxwIHRoZSBib2FyZCBvZiBCeXRlbCB0byBwbGFuIHRoZSBudW1iZXIgb2Ygb2ZmaWNlIGJ1aWxkaW5ncyBhbmQgdGhlaXIgc2l6ZSBpbiBhY2NvcmRhbmNlIHdpdGggdGhlIGFmb3JlbWVudGlvbmVkIHJlcXVpcmVtZW50cy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgd2hpY2g6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIGVtcGxveWVlcyYjMzk7IHBob25lIG51bWJlciBsaXN0cyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dDxcL2xpPlxyXG5cdDxsaT5jYWxjdWxhdGVzIHRoZSBtYXhpbWFsIG51bWJlciBvZiBvZmZpY2UgYnVpbGRpbmdzIGFuZCB0aGVpciBzaXplcywgc2F0aXNmeWluZyBib2FyZCYjMzk7cyBjb25kaXRpb25zPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb3V0Y29tZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzOiBuIGFuZCBtICgyICZsZTsgbiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBtICZsZTsgMiAwMDAgMDAwKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgQnl0ZWwgZW1wbG95ZWVzIGFuZCB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGVtcGxveWVlcyB3aG8gaGF2ZSB0aGVpciBudW1iZXJzIGluIGNvbXBhbnkgcGhvbmVzLCByZXNwZWN0aXZlbHkuIFRoZSBlbXBsb3llZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBwYWlyIG9mIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+IGFuZCBiPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsdDsgYjxzdWI+aTxcL3N1Yj4gJmxlOyBuIGZvciAxICZsZTsgaSAmbGU7IG0pLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGRlbm90aW5nIHRoYXQgZW1wbG95ZWVzIGFpIGFuZCBiaSBoYXZlIHRoZWlyIG51bWJlcnMgKHJlY2lwcm9jYWxseSkgaW4gY29tcGFueSBwaG9uZXMmIzM5OyBtZW1vcnkuIEVhY2ggcGFpciBvZiBpbnRlZ2VycyBkZW5vdGluZyBhIHBhaXIgb2YgZW1wbG95ZWVzIHNoYWxsIG9jY3VyIG9uY2UgYXQgdGhlIG1vc3QgaW4gdGhlIHN0YW5kYXJkIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1heGltYWwgbnVtYmVyIG9mIG9mZmljZSBidWlsZGluZ3MgdGhhdCBCeXRlbCBzaG91bGQgcmVudC4gVGhlIHNlY29uZCBzaG91bGQgY29udGFpbiBhIG5vbi1kZWNyZWFzaW5nIHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc2luZ2Ugc3BhY2VzLCBkZW5vdGluZyB0aGUgc2l6ZXMgb2YgdGhlIG9mZmljZSBidWlsZGluZ3MgKGkuZS4gdGhlIG51bWJlcnMgb2YgZW1wbG95ZWVzIHdvcmtpbmcgdGhlcmUpLiBTaG91bGQgdGhlcmUgZXhpc3QgbW9yZSB0aGFuIG9uZSBjb3JyZWN0IGFuc3dlciAtIHdyaXRlIG91dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IjxwPkFuIGV4ZW1wbGFyeSBjb3JyZWN0IGRpc3RyaWJ1dGlvbiBvZiBlbXBsb3llZXMgaW4gdGhlIG9mZmljZSBidWlsZGluZ3M6IGVtcGxveWVlIG51bWJlciA0IGluIHRoZSBmaXJzdCBvZmZpY2UsIG51bWJlcnMgNSBhbmQgNyBpbiB0aGUgc2Vjb25kIG9mZmljZSwgbnVtYmVycyAxLCAyLCAzLCA2IGluIHRoZSB0aGlyZCBvZmZpY2UgYnVpbGRpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Polish Olympiad in Informatics > POI 2006/2007 > Stage 1 2번

  • 문제의 오타를 찾은 사람: andy627
  • 문제를 번역한 사람: author10