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

문제

소셜 네트워크는 이제 우리 삶의 일부가 되어버렸다. 이러한 소셜 네트워크를 분석하는 김동규 석사과정은 흥미로운 현상을 발견했다. 바로 친구 관계의 수가 급속도로 증가한다는 것이다.

예로부터 우리의 조상님들은 "친구의 친구는 나의 친구"라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구 관계는 상대방이 수락을 해야 되고, 총 1일이 걸린다.

예를 들어, A와 B가 친구라면, A는 B가 어제 또는 그 이전에 만든 친구만 볼 수 있다.

모든 친구관계는 대칭이다. 즉, A와 B의 친구라면, B도 A의 친구이다.

김동규가 분석하는 소셜 네트워크에서는 한 번 친구 관계가 맺어졌으면, 이것을 깰 수 없다.

사람의 수와 지금 친구 관계가 주어졌을 때, 모든 사람이 서로 친구가 되는데 걸리는데 며칠이 걸리는지 구하는 프로그램을 작성하시오. 또한, 매일 매일 새로운 친구 관계가 얼마나 생기는지 구해서 출력하시오.

입력

첫째 줄에 사람의 수 N과 처음 친구 관계의 수 M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N-1)/2)

둘째 줄부터 M개의 줄에는 두 정수 A와 B가 주어진다. (1 ≤ A ≤ N, 1 ≤ B ≤ N, A < B). 이것은 A와 B가 친구라는 것을 의미한다. 항상 모든 사람이 서로 친구가 될 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 모든 사람이 서로 친구가 되는데 며칠이 걸리는지 출력한다. 이 값을 K라고 하자.

다음 K개의 줄에는 몇 명의 새로운 친구 관계가 생기는지, 첫째날부터, K번째 날까지 한 줄에 하나씩 출력한다. 

예제 입력 1

3 2
1 2
2 3

예제 출력 1

1
1

예제 입력 2

5 4
1 2
2 3
3 4
4 5

예제 출력 2

2
3
3

예제 입력 3

5 4
1 2
1 3
1 4
1 5

예제 출력 3

1
6
W3sicHJvYmxlbV9pZCI6IjMwOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMxNWNcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWIyOTQgXHVjNzc0XHVjODFjIFx1YzZiMFx1YjlhYyBcdWMwYjZcdWM3NTggXHVjNzdjXHViZDgwXHVhYzAwIFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWI5N2MgXHViZDg0XHVjMTFkXHVkNTU4XHViMjk0IFx1YWU0MFx1YjNkOVx1YWRkYyBcdWMxMWRcdWMwYWNcdWFjZmNcdWM4MTVcdWM3NDAgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1ZDYwNFx1YzBjMVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YmMxNFx1Yjg1YyBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFlMDlcdWMxOGRcdWIzYzRcdWI4NWMgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViODVjXHViZDgwXHVkMTMwIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWM4NzBcdWMwYzFcdWIyZDhcdWI0ZTRcdWM3NDAgJnF1b3Q7XHVjZTVjXHVhZDZjXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjI5NCBcdWIwOThcdWM3NTggXHVjZTVjXHVhZDZjJnF1b3Q7XHViNzdjXHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YjllNFx1Yzc3YyBcdWM4NzBcdWMwYzFcdWIyZDhcdWI0ZTRcdWM3NTggXHViOWQwXHVjNTAwXHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNlNWNcdWFkNmMgXHViYWE5XHViODVkXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjZTVjXHVhZDZjXHViODVjIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YjI5NCBcdWMwYzFcdWIzMDBcdWJjMjlcdWM3NzQgXHVjMjE4XHViNzdkXHVjNzQ0IFx1ZDU3NFx1YzU3YyBcdWI0MThcdWFjZTAsIFx1Y2QxZCAxXHVjNzdjXHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQVx1YzY0MCBCXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YmE3NCwgQVx1YjI5NCBCXHVhYzAwIFx1YzViNFx1YzgxYyBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWI5Y2NcdWI0ZTAgXHVjZTVjXHVhZDZjXHViOWNjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjZTVjXHVhZDZjXHVhZDAwXHVhY2M0XHViMjk0IFx1YjMwMFx1Y2U2ZFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBBXHVjNjQwIEJcdWM3NTggXHVjZTVjXHVhZDZjXHViNzdjXHViYTc0LCBCXHViM2M0IEFcdWM3NTggXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlNDBcdWIzZDlcdWFkZGNcdWFjMDAgXHViZDg0XHVjMTFkXHVkNTU4XHViMjk0IFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTVjIFx1YmM4OCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YjlmYVx1YzViNFx1Yzg0Y1x1YzczY1x1YmE3NCwgXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YWU3MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzljMFx1YWUwOCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0XHViMzcwIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjYxMFx1ZDU1YywgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHVjMGRkXHVhZTMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWNjOThcdWM3NGMgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwLCAxICZsZTsgTSAmbGU7IE4qKE4tMSlcLzIpPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBOLCAxICZsZTsgQiAmbGU7IE4sIEEgJmx0OyBCKS4gXHVjNzc0XHVhYzgzXHVjNzQwIEFcdWM2NDAgQlx1YWMwMCBcdWNlNWNcdWFkNmNcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MThcdWIyOTRcdWIzNzAgXHViYTcwXHVjZTYwXHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDQgS1x1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhODcgXHViYTg1XHVjNzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzBkZFx1YWUzMFx1YjI5NFx1YzljMCwgXHVjY2FiXHVjOWY4XHViMGEwXHViZDgwXHVkMTMwLCBLXHViYzg4XHVjOWY4IFx1YjBhMFx1YWU0Y1x1YzljMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZFSlMiLCJkZXNjcmlwdGlvbiI6IjxwPlNvY2lhbCBuZXR3b3JrcyBvbiB0aGUgSW50ZXJuZXQgYmVjYW1lIGEgcGFydCBvZiB0aGUgZXZlcnlkYXkgbGlmZS4gT25lIG9mIHRoZSBpbnRlcmVzdGluZyBwaGVub21lbmEgaXMgdGhhdCB0aGUgbnVtYmVyIG9mIGZyaWVuZHNoaXAgaXMgaW5jcmVhc2luZyByYXBpZGx5LiBBY2NvcmRpbmcgdG8gdGhlIG9sZCAmbGRxdW87YSBmcmllbmQgb2YgYSBmcmllbmQgaXMgbXkgZnJpZW5kJnJkcXVvOywgZWFjaCBwZXJzb24gZXZlcnkgZGF5IGNoZWNrcyB0aGUgbGlzdCBvZiBmcmllbmRzIG9mIGhpcyBmcmllbmRzIGFuZCBhZGRzIG5ldyBwZW9wbGUgdG8gaGlzIGxpc3QuIEl0IHRha2VzIDEgZGF5IHRvIGNvbmZpcm0gdGhlIG5ldyBmcmllbmRzaGlwLiBTbywgaWYgQSBhbmQgQiBhbmQgZnJpZW5kcyB0aGVuIHBlcnNvbiBBIHNlZXMgb25seSBmcmllbmRzaGlwcyBvZiBwZXJzb24gQiB0aGF0IHdlcmUgbWFkZSB5ZXN0ZXJkYXkgb3IgYmVmb3JlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGwgZnJpZW5kc2hpcHMgYXJlIHN5bW1ldHJpYyAmbmRhc2g7IGlmIEEgaXMgYSBmcmllbmQgb2YgQiB0aGVuIEIgaXMgYSBmcmllbmQgb2YgQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QXMgc29jaWFsIG5ldHdvcmsgd2UgYXJlIG9ic2VydmluZyBpbiB0aGlzIHRhc2sgZG9lc24mIzM5O3QgYWxsb3cgZnJpZW5kc2hpcHMgdG8gYmUgYnJva2VuIGF0IHNvbWUgcG9pbnQgZXZlcnlvbmUgd2lsbCBiZSBmcmllbmQgdG8gZXZlcnlvbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgZGF5cyB1bnRpbCB0aGF0IGhhcHBlbnMuIEZvciBlYWNoIGRheSBvdXRwdXQgdGhlIG51bWJlciBvZiBuZXcgZnJpZW5kc2hpcHMgdGhhdCB3ZXJlIG1hZGUgdGhhdCBkYXkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyA1MCwgMSAmbGU7IE0gJmxlOyBOKihOJm5kYXNoOzEpXC8yKSwgdGhlIG51bWJlciBvZiB1c2VycyBhbmQgaW5pdGlhbCBudW1iZXIgb2YgZnJpZW5kc2hpcHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE0gbGluZXMgY29udGFpbiB0d28gbnVtYmVycyBlYWNoIEEgYW5kIEIgKDEgJmxlOyBBICZsZTsgTiwgMSAmbGU7IEIgJmxlOyBOLCBBICZsdDsgQikgdGhhdCBkZXNjcmliZSBmcmllbmRzaGlwcyBiZXR3ZWVuIHVzZXJzIEEgYW5kIEIuIFRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBzb2x1dGlvbiB3aWxsIGFsd2F5cyBleGlzdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvdXRwdXQgb25lIGludGVnZXIsIHRoZSBudW1iZXIgb2YgZGF5cyBLIHVudGlsIGV2ZXJ5b25lIHdpbGwgYmUgZnJpZW5kIHRvIGV2ZXJ5b25lLiBJbiBlYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgb3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgbnVtYmVyIG9mIGZyaWVuZHNoaXBzIHRoYXQgd2VyZSBtYWRlIHRoYXQgZGF5LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=