시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB8838212925875719.189%

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2
W3sicHJvYmxlbV9pZCI6IjEzMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzggXHVkNTc0XHVkMGI5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWNlZTQgXHVhZTQwXHVjOWMwXHViYmZjXHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjNWI0XHViMjkwIFx1ZDY4Y1x1YzBhY1x1Yjk3YyBcdWQ1NzRcdWQwYjlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVkNjhjXHVjMGFjXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjZWY0XHVkNGU4XHVkMTMwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWU0MFx1YzljMFx1YmJmY1x1Yzc0MCBcdWFkYzBcdWNjMmVcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NWMgXHViYzg4XHVjNzU4IFx1ZDU3NFx1ZDBiOVx1YzczY1x1Yjg1YyBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWQ1NzRcdWQwYjkgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1ZDU3NFx1ZDBiOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQ2OGNcdWMwYWNcdWM3NTggXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IFx1YzJlMFx1YjhiMFx1ZDU1OFx1YjI5NCBcdWFkMDBcdWFjYzRcdWM2NDAsIFx1YzJlMFx1YjhiMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDAwXHVhY2M0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAsIEFcdWFjMDAgQlx1Yjk3YyBcdWMyZTBcdWI4YjBcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IEJcdWI5N2MgXHVkNTc0XHVkMGI5XHVkNTU4XHViYTc0LCBBXHViM2M0IFx1ZDU3NFx1ZDBiOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YzE4Y1x1YjlhY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM3NTggXHVjMmUwXHViOGIwXHVkNTU4XHViMjk0IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1ZDU3NFx1ZDBiOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBOXHVhY2ZjIE1cdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBOXHVjNzQwIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCwgTVx1Yzc0MCAxMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzJlMFx1YjhiMFx1ZDU1OFx1YjI5NCBcdWFkMDBcdWFjYzRcdWFjMDAgQSBCXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI0XHViYTcwLCAmcXVvdDtBXHVhYzAwIEJcdWI5N2MgXHVjMmUwXHViOGIwXHVkNTVjXHViMmU0JnF1b3Q7XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHVhZTQwXHVjOWMwXHViYmZjXHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVkNTc0XHVkMGI5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEzMjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCcmVha2luZyBpbiIsImRlc2NyaXB0aW9uIjoiPHA+TWF5Y28gaGFzIHJlY2VudGx5IGJlZW4gaGlyZWQgYXMgYSBzZWN1cml0eSBjb25zdWx0YW50IGZvciBhIHdlbGwta25vd24gc29mdHdhcmUgY29tcGFueS4gQXQgdGhlIG1vbWVudCwgaGUmcnNxdW87cyB3b3JraW5nIG9uIGhpcyBmaXJzdCBhc3NpZ25tZW50ICZuZGFzaDsgdHJ5aW5nIHRvIGRldGVybWluZSB3aGljaCBvZiB0aGUgY29tcGFueSZyc3F1bztzIHNlcnZlcnMgd291bGQgYmUgdGhlIGJlc3QgdGFyZ2V0cyBmb3IgcG90ZW50aWFsIGF0dGFja2Vycy4gSXQgaXMgYSBiaXQgZGlmZmljdWx0LCB0aG91Z2gsIGJlY2F1c2Ugc29tZSBvZiB0aGUgc2VydmVycyAmbGRxdW87dHJ1c3QmcmRxdW87IHNvbWUgb2YgdGhlIG90aGVycy4gSWYgYW4gYXR0YWNrZXIgY29tcHJvbWlzZXMgYSBzZXJ2ZXIsIGhlIG9yIHNoZSBjYW4gYWxzbyBmcmVlbHkgYWNjZXNzIGFsbCBzZXJ2ZXJzIHRoYXQgdHJ1c3QgaXQgKGFuZCBzZXJ2ZXJzIHRoYXQgdHJ1c3QgdGhlbSwgYW5kIHNvIG9uKS48XC9wPlxyXG5cclxuPHA+QnkgZGVmaW5pdGlvbiwgdGhlIGltcG9ydGFuY2Ugb2YgYSBzZXJ2ZXImbmJzcDtTJm5ic3A7aXMgdGhlIG51bWJlciBvZiBzZXJ2ZXJzIHRoZSBhdHRhY2tlciB3b3VsZCBiZSBhYmxlIHRvIGFjY2VzcyBpZiBoZSBjb21wcm9taXNlZCZuYnNwO1MuIFRoZSBtb3N0IGltcG9ydGFudCBzZXJ2ZXJzIGFyZSB0aG9zZSB3aXRoIHRoZSBoaWdoZXN0IGltcG9ydGFuY2UuIChOb3RlIHRoYXQgdGhlcmUgY2FuIGJlIG1vcmUgdGhhbiBvbmUgbW9zdCBpbXBvcnRhbnQgc2VydmVyLiBUaGlzIGlzIGFsc28gaWxsdXN0cmF0ZWQgaW4gdGhlIGV4YW1wbGUgYmVsb3cuKTxcL3A+XHJcblxyXG48cD5UaGUgbmV0d29yayBjb25zaXN0cyBvZiZuYnNwO04mbmJzcDtjb21wdXRlcnMsIG51bWJlcmVkIDEgdG8mbmJzcDtOLCBpbmNsdXNpdmUuIFRoZSB0cnVzdCBiZXR3ZWVuIGNvbXB1dGVycyBpcyBkZXNjcmliZWQgYnkmbmJzcDtNJm5ic3A7b3JkZXJlZCBwYWlycyAoQSxCKSBvZiBudW1iZXJzLCBkZW5vdGluZyB0aGF0IGNvbXB1dGVyJm5ic3A7QSZuYnNwO3RydXN0cyBjb21wdXRlciZuYnNwO0IuIFRoZSB0cnVzdCBpcyBub3QgYXNzdW1lZCB0byBiZSBtdXR1YWwgJm5kYXNoOyBpLmUuLCBpZiBhIGNvbXB1dGVyJm5ic3A7QSZuYnNwO3RydXN0cyBjb21wdXRlciZuYnNwO0IsIGl0IGRvZXMgbm90IG5lY2Vzc2FyaWx5IGltcGx5IHRoYXQgY29tcHV0ZXImbmJzcDtCJm5ic3A7dHJ1c3RzIGNvbXB1dGVyJm5ic3A7QS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXJzJm5ic3A7TiZuYnNwO2FuZCZuYnNwO00uIEVhY2ggb2YgdGhlIGZvbGxvd2luZyZuYnNwO00mbmJzcDtsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMsJm5ic3A7QSZuYnNwO2FuZCZuYnNwO0IsIGRlbm90aW5nIHRoYXQgY29tcHV0ZXImbmJzcDtBJm5ic3A7dHJ1c3RzIGNvbXB1dGVyJm5ic3A7Qi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNoYWxsIGNvbnRhaW4gb25lIGxpbmUgd2l0aCB0aGUgbnVtYmVycyBvZiBhbGwgb2YgdGhlIG1vc3QgaW1wb3J0YW50IHNlcnZlcnMuIFRoZSBudW1iZXJzIG11c3QgYmUgbGlzdGVkIGluIGluY3JlYXNpbmcgb3JkZXIgYW5kIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxMCwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBBLCBCICZsZTsgTjxcL2xpPlxyXG5cdDxsaT5BICZuZTsgQjxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

Contest > Internet Problem Solving Contest > IPSC 2008 B번