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

문제

원장선생님께서는 1부터 N까지 번호가 붙은 N(K ≤ N ≤ 900)명의 학생들 중에서 K(1 ≤ K ≤ 62)명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 정보를 F(1 ≤ F ≤ 5,600)개를 주시며 K명을 선발하라고 부탁하였다.

고은 조교를 도와 소풍을 가게 될 K명의 학생들을 결정하시오.

입력

첫째 줄에 공백으로 분리된 세 정수 K, N, F가 주어진다. 다음 F개의 줄에는 서로 친구 관계인 두 사람의 번호가 주어진다. 친구 관계는 상호적인 관계이므로 2번 학생이 4번 학생을 좋아하면 4번 학생도 2번 학생을 좋아한다. 같은 친구 관계가 여러 번 주어지는 경우는 없다.

출력

만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 학생의 번호가 제일 작은 것을 출력한다. 첫 번째 학생의 번호가 같은 경우라면, 두 번째 학생의 번호가 작은 경우를 출력하고, 이와 같은 식으로 출력한다.

예제 입력 1

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

예제 출력 1

1
2
3
6
W3sicHJvYmxlbV9pZCI6IjIwMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWQ0OGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMFx1YzdhNVx1YzEyMFx1YzBkZFx1YjJkOFx1YWVkOFx1YzExY1x1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1Yzc0MCBOKEsgJmxlOyBOICZsZTsgOTAwKVx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIEsoMSAmbGU7IEsgJmxlOyA2MilcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YzE4Y1x1ZDQ4ZFx1YzVkMCBcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVhZWQ4XHVjMTFjXHViMjk0IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWMyZjhcdWM2YzBcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHViYTc0IFx1YzU0OFx1YjQxOFx1YmJjMFx1Yjg1YyBcdWMxOGNcdWQ0OGRcdWM3NDQgXHVhYzA4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjIFx1Y2U1Y1x1YWQ2YyBcdWMwYWNcdWM3NzRcdWM3NzRcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWFlZDhcdWMxMWNcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1Yzc3Y1x1Yzc0NCBcdWM3NzRcdWJjODhcdWM1ZDAgXHVjODcwXHVhZDUwXHViODVjIFx1Y2MzOFx1YWMwMFx1ZDU1YyBcdWFjZTBcdWM3NDBcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIEYoMSAmbGU7IEYgJmxlOyA1LDYwMClcdWFjMWNcdWI5N2MgXHVjOGZjXHVjMmRjXHViYTcwIEtcdWJhODVcdWM3NDQgXHVjMTIwXHViYzFjXHVkNTU4XHViNzdjXHVhY2UwIFx1YmQ4MFx1ZDBjMVx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHVjNzQwIFx1Yzg3MFx1YWQ1MFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjMThjXHVkNDhkXHVjNzQ0IFx1YWMwMFx1YWM4YyBcdWI0MjAgS1x1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHVhY2IwXHVjODE1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDFjIFx1YzEzOCBcdWM4MTVcdWMyMTggSywgTiwgRlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBGXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yzc3OCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWIyOTQgXHVjMGMxXHVkNjM4XHVjODAxXHVjNzc4IFx1YWQwMFx1YWNjNFx1Yzc3NFx1YmJjMFx1Yjg1YyAyXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc3NCA0XHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWJhNzQgNFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWIzYzQgMlx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCBLXHViYTg1XHVjNzU4IFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWM3NzggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTU5XHVjMGRkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4MWNcdWM3N2MgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTU5XHVjMGRkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViNzdjXHViYTc0LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3ByaW5nIFZhY2F0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgd29uIHRoZSBXQ09XIHJhZGlvIHN0YXRpb24gY2FsbC1pbiBzd2VlcHN0YWtlcyBncmFuZCBwcml6ZTogSyAoMSAmbHQ7PSBLICZsdDs9IDYyKSBwbGFuZSB0aWNrZXRzIGZvciBhIHZhY2F0aW9uIGdldGF3YXkgdG8gc3VubnkgQm92aW5lLCBUWCwgaG9tZSBvZiB0aGUgd29ybGQmIzM5O3MgbGFyZ2VzdCBjb3cgd2F0ZXJzbGlkZS48XC9wPlxyXG5cclxuPHA+RkogaGFzIGRlY2lkZWQgdG8gZ2l2ZSB0aGUgdGlja2V0cyB0byBLIG9mIGhpcyBOIChLICZsdDs9IE4gJmx0Oz0gOTAwKSBjb3dzICh3aG8sIGZvciB0aGUgcHVycG9zZXMgb2YgdGhpcyBwcm9ibGVtLCBhcmUgbnVtYmVyZWQgMS4uTikuICZuYnNwO0hlIHdhbnRzIHRvIHNlbmQgb25seSBjb3dzIHdobyBhcmUgYWxsIGZyaWVuZHMgd2l0aCBlYWNoIG90aGVyOyB5b3UgYXJlIHByb3ZpZGVkIGEgbGlzdCBvZiBGICgxICZsdDs9IEYgJmx0Oz0gNTYwMCkgZnJpZW5kc2hpcHMuPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgc2V0IG9mIEsgY293LWZyaWVuZHMgdGhhdCB3aWxsIGVuam95IHRoZSBmYWJ1bG91cyB2YWNhdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IEssIE4sIGFuZCBGLjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5GKzE6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgZGVzY3JpYmUgZnJpZW5kc2hpcCBiZXR3ZWVuIHRoZSB0d28gbmFtZWQgY293cy4gRnJpZW5kc2hpcCBpcyBjb21tdXRhdGl2ZSwgaWYgY293IDIgbGlrZXMgY293IDQgdGhlbiBjb3cgNCBsaWtlcyBjb3cgMi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCAtMSBpZiBubyBzZXQgb2YgSyBmcmllbmRzIGV4aXN0cy4gJm5ic3A7T3RoZXJ3aXNlLCBvdXRwdXQgdGhlIHNldCBvZiBLIGNvdy1mcmllbmRzIGluIGFzY2VuZGluZyBvcmRlciwgb25lIGludGVnZXIgcGVyIG91dHB1dCBsaW5lLiAmbmJzcDtJZiBtb3JlIHRoYW4gb25lIHNldCBvZiBLIGZyaWVuZHMgZXhpc3RzLCBvdXRwdXQgdGhlIHNldCB3aG9zZSBmaXJzdCBlbGVtZW50IGlzIHNtYWxsZXN0IChvciBzZWNvbmQgZWxlbWVudCBpcyBzbWFsbGVzdCBpZiB0aGUgZmlyc3QgZWxlbWVudHMgYXJlIHRoZSBzYW1lLCBldGMuKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO December 2003 Contest > Green 3번