시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB350937036.269%

문제

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

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

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

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

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

입력

첫째 줄 학생들의 수 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+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjLCBcdWM2ZDBcdWM3YTVcdWIyZDhcdWM3NDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmMxOFx1Yzc0NCBcdWM3OThcdWFjOGMgXHViMDk4XHViMjA0XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YzJlMFx1YjJlNC4gXHViMmU0XHViOTc4IFx1YmMxOFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHViMDdjXHViOWFjXHViMjk0IFx1YmE1NFx1YzJlMFx1YzgwMFx1Yjg1YyBcdWIzMDBcdWQ2NTRcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjLCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjMTFjXHViODVjXHVjNzU4IFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWIwN2NcdWI5YWMgXHVjMTFjXHViODVjXHVjNzU4IFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmMxOFx1Yzc0NCBcdWQzYjhcdWMxMzFcdWQ1NThcdWI4MjRcdWJhNzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMyMTggblx1YWNmYywgXHVjMTFjXHViODVjIFx1YmE1NFx1YzJlMFx1YzgwMCBcdWM1NDRcdWM3NzRcdWI1MTRcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTQgXHVjMzBkXHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTAwLDAwMC4gMSAmbGU7IG0gJmxlOyAyLDAwMCwwMDApIFx1Yzc3NFx1ZDZjNCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViYTU0XHVjMmUwXHVjODAwIFx1YzU0NFx1Yzc3NFx1YjUxNFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNCBcdWJjODhcdWQ2MzhcdWM3NTggXHVjMzBkXHVjNzc0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1Yzc3NFx1YzBjMSBuXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkM2I4XHVjMTMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzE4XHVjNzc0IFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0LCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkM2I4XHVjMTMxXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWFjMDEgXHViYzE4XHViY2M0IFx1Yzc3OFx1YzZkMFx1YzIxOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD40XHViYzg4IFx1ZDU1OVx1YzBkZCBcdWQ2M2NcdWM3OTAgXHVkNTVjIFx1YmMxOCwgNVx1YmM4OFx1YWNmYyA3XHViYzg4IFx1ZDU1OVx1YzBkZCBcdWI0NThcdWM3NzRcdWMxMWMgXHVkNTVjIFx1YmMxOCwgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDU1OVx1YzBkZCBcdWIxMjQgXHViYTg1XHVjNzc0XHVjMTFjIFx1ZDU1YyBcdWJjMThcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YmMxOFx1Yzc0NCBcdWQzYjhcdWMxMzFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTc0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9mZmljZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVsIGlzIGEgbW9iaWxlIHRlbGVwaG9ueSBwb3RlbnRhdGUuIEVhY2ggZW1wbG95ZWUgaGFzIGJlZW4gaXNzdWVkIGEgY29tcGFueSBwaG9uZSwgdGhlIG1lbW9yeSBvZiB3aGljaCBob2xkcyB0aGUgbnVtYmVycyBvZiBzb21lIG9mIGhpcyBjby13b3JrZXJzIChhbGwgb2YgdGhlbSBoYXZlIGhpcyBudW1iZXIgaW4gdGhlaXIgcGhvbmVzIGFzIHdlbGwpLiBEdWUgdG8gZHluYW1pYyBncm93dGggb2YgdGhlaXIgb3BlcmF0aW9ucyB0aGUgYm9hcmQgb2YgZGlyZWN0b3JzIGludGVuZHMgdG8gbW92ZSBjb21wYW55IGhlYWRxdWF0ZXJzIHRvIG5ldyBvZmZpY2UgYnVpbGRpbmdzLiBJdCBoYXMgYmVlbiBkZWNpZGVkIC0gaW4gb3JkZXIgdG8gYm9vc3Qgd29yayBlZmZpY2llbmN5IC0gdGhhdCBldmVyeSBwYWlyIG9mIGVtcGxveWVlcyB3b3JraW5nIGluIGRpZmZlcmVudCBidWlsZGluZ3Mgc2hvdWxkIGtub3cgKHJlY2lwcm9jYWxseSkgZWFjaCBvdGhlcnMgcGhvbmUgbnVtYmVyIGkuZS4gdGhlIG1lbW9yeSBvZiB0aGVpciBjb21wYW55IHBob25lIG91Z2h0IHRvIGhvbGQgbmVjZXNzYXJ5IHBob25lIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPlNpbXVsdGFuZW91c2x5LCB0aGUgYm9hcmQgaGF2ZSBkZWNpZGVkIHRvIHJlbnQgYXMgbWFueSBvZmZpY2UgYnVpbGRpbmdzIGFzIHBvc3NpYmxlIHRvIGVuc3VyZSBnb29kIHdvcmtpbmcgY29uZGl0aW9ucy4gSGVscCB0aGUgYm9hcmQgb2YgQnl0ZWwgdG8gcGxhbiB0aGUgbnVtYmVyIG9mIG9mZmljZSBidWlsZGluZ3MgYW5kIHRoZWlyIHNpemUgaW4gYWNjb3JkYW5jZSB3aXRoIHRoZSBhZm9yZW1lbnRpb25lZCByZXF1aXJlbWVudHMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiBlbXBsb3llZXMmIzM5OyBwaG9uZSBudW1iZXIgbGlzdHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQ8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyB0aGUgbWF4aW1hbCBudW1iZXIgb2Ygb2ZmaWNlIGJ1aWxkaW5ncyBhbmQgdGhlaXIgc2l6ZXMsIHNhdGlzZnlpbmcgYm9hcmQmIzM5O3MgY29uZGl0aW9uczxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIG91dGNvbWUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VyczogbiBhbmQgbSAoMiAmbGU7IG4gJmxlOyAxMDAgMDAwLCAxICZsZTsgbSAmbGU7IDIgMDAwIDAwMCksIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIEJ5dGVsIGVtcGxveWVlcyBhbmQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBlbXBsb3llZXMgd2hvIGhhdmUgdGhlaXIgbnVtYmVycyBpbiBjb21wYW55IHBob25lcywgcmVzcGVjdGl2ZWx5LiBUaGUgZW1wbG95ZWVzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG0gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgcGFpciBvZiBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbHQ7IGI8c3ViPmk8XC9zdWI+ICZsZTsgbiBmb3IgMSAmbGU7IGkgJmxlOyBtKSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCBkZW5vdGluZyB0aGF0IGVtcGxveWVlcyBhaSBhbmQgYmkgaGF2ZSB0aGVpciBudW1iZXJzIChyZWNpcHJvY2FsbHkpIGluIGNvbXBhbnkgcGhvbmVzJiMzOTsgbWVtb3J5LiBFYWNoIHBhaXIgb2YgaW50ZWdlcnMgZGVub3RpbmcgYSBwYWlyIG9mIGVtcGxveWVlcyBzaGFsbCBvY2N1ciBvbmNlIGF0IHRoZSBtb3N0IGluIHRoZSBzdGFuZGFyZCBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXI6IHRoZSBtYXhpbWFsIG51bWJlciBvZiBvZmZpY2UgYnVpbGRpbmdzIHRoYXQgQnl0ZWwgc2hvdWxkIHJlbnQuIFRoZSBzZWNvbmQgc2hvdWxkIGNvbnRhaW4gYSBub24tZGVjcmVhc2luZyBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IHNpbmdlIHNwYWNlcywgZGVub3RpbmcgdGhlIHNpemVzIG9mIHRoZSBvZmZpY2UgYnVpbGRpbmdzIChpLmUuIHRoZSBudW1iZXJzIG9mIGVtcGxveWVlcyB3b3JraW5nIHRoZXJlKS4gU2hvdWxkIHRoZXJlIGV4aXN0IG1vcmUgdGhhbiBvbmUgY29ycmVjdCBhbnN3ZXIgLSB3cml0ZSBvdXQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5BbiBleGVtcGxhcnkgY29ycmVjdCBkaXN0cmlidXRpb24gb2YgZW1wbG95ZWVzIGluIHRoZSBvZmZpY2UgYnVpbGRpbmdzOiBlbXBsb3llZSBudW1iZXIgNCBpbiB0aGUgZmlyc3Qgb2ZmaWNlLCBudW1iZXJzIDUgYW5kIDcgaW4gdGhlIHNlY29uZCBvZmZpY2UsIG51bWJlcnMgMSwgMiwgMywgNiBpbiB0aGUgdGhpcmQgb2ZmaWNlIGJ1aWxkaW5nLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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