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

문제

안녕 친구들? 내 이름은 홍즈. 세계에서 제일 유명한 탐정이지. 요즘 내가 가는 곳마다 살인 사건이 끊이질 않아서 고민이야(웃음)! 서로에게 상처밖에 주지 못하는 불쌍한 사람들... 어쨋든 오늘도 나는 살인 사건을 찾아 헤매이고 있지. 돈을 벌어야 하니까.

나는 지금까지 탐정을 하면서 얻은 경험으로 사람이 일으키는 사건의 인과관계를 간단하게 압축할 수 있었어. 예를 들어 사건 A가 일어났다면 무조건 사건 B가 일어나야 한다는 것을 알고 있어. 이런 관계를 A → B라고 나타내자. 사건이 여러개 이어져서 A → B → C와 같은 관계가 있을 수도 있어, 하지만 A → B → C → ... → A 같은식으로 순환하는 관계는 없어. 그리고 만약 A → C이고 B → C라고 하고 사건 C가 일어났다고 하자. 이런 경우에는 사건 A나 사건 B중 하나는 일어났을거라는 사실을 알 수 있어.

오늘도 오늘의 살인 사건이 일어났군. 지금 증거들을 수집했어, 이걸로 나는 총 N개의 사건이 일어났다는 것을 알 수 있었어. 이것으로 나는 무조건 일어났을 다른 사건들이 더 있다는 사실을 알게 되었어. 나는 지성과 경험을 모두 겸비한 탐정이니까. 당신도 과연 알 수 있을까?

입력

첫 번째 줄에 일어날 수 있는 사건의 개수 D (1 ≤ D ≤ 1000), 사건들 간의 관계의 개수 M (1 ≤ M ≤ 100000), 그리고 일어난 사건의 개수 N (1 ≤ N ≤ D)이 공백으로 구분되어 주어진다.

다음 M개의 줄에는 두 정수 A와 B(1 ≤ A, B ≤ D)가 주어지는데 이는 사건 A,B가  A → B인 관계에 있음을 나타낸다.

마지막으로 다음 N개의 줄에는 일어난 사건을 나타내는 정수 X (1 ≤ X ≤ D)가 주어진다.

출력

무조건 일어나야 하는 사건을 한 줄에 공백으로 구분하여 출력한다. 순서는 상관없다.

예제 입력 1

3 2 1
1 2
2 3
2

예제 출력 1

1 2 3

예제 입력 2

3 2 1
1 3
2 3
3

예제 출력 2

3

예제 입력 3

4 4 1
1 2
1 3
2 4
3 4
4

예제 출력 3

1 2 3 4

사건 4가 일어났는데, 사건 {2,3}중에 어떤 사건이 4를 일으켰는지 알 수 없다. 그러나 사건 {2,3}이 일어나기 위해서는 사건 1이 일어나야 하므로, 홍즈는 어쨌든 사건 1이 일어났어야만 한다는 사실을 알 수 있고, 이로 인해서 사건 2,3,4도 일어났어야 한다는 사실을 알 수 있다.

W3sicHJvYmxlbV9pZCI6IjI4OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhODVcdWQwZDBcdWM4MTUgXHVkNjRkXHVjOTg4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDhcdWIxNTUgXHVjZTVjXHVhZDZjXHViNGU0PyBcdWIwYjQgXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDY0ZFx1Yzk4OC4gXHVjMTM4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzgxY1x1Yzc3YyZuYnNwO1x1YzcyMFx1YmE4NVx1ZDU1YyBcdWQwZDBcdWM4MTVcdWM3NzRcdWM5YzAuIFx1YzY5NFx1Yzk5OCBcdWIwYjRcdWFjMDAgXHVhYzAwXHViMjk0IFx1YWNmM1x1YjljOFx1YjJlNCBcdWMwYjRcdWM3NzggXHVjMGFjXHVhYzc0XHVjNzc0IFx1YjA0YVx1Yzc3NFx1YzljOCBcdWM1NGFcdWM1NDRcdWMxMWMgXHVhY2UwXHViYmZjXHVjNzc0XHVjNTdjKFx1YzZjM1x1Yzc0YykhIFx1YzExY1x1Yjg1Y1x1YzVkMFx1YWM4YyBcdWMwYzFcdWNjOThcdWJjMTZcdWM1ZDAgXHVjOGZjXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWJkODhcdWMzMGRcdWQ1NWMgXHVjMGFjXHViNzhjXHViNGU0Li4uJm5ic3A7XHVjNWI0XHVjYTBiXHViNGUwJm5ic3A7XHVjNjI0XHViMjk4XHViM2M0IFx1YjA5OFx1YjI5NCZuYnNwO1x1YzBiNFx1Yzc3OCBcdWMwYWNcdWFjNzRcdWM3NDQgXHVjYzNlXHVjNTQ0IFx1ZDVlNFx1YjllNFx1Yzc3NFx1YWNlMCBcdWM3ODhcdWM5YzAuIFx1YjNjOFx1Yzc0NCBcdWJjOGNcdWM1YjRcdWM1N2MgXHVkNTU4XHViMmM4XHVhZTRjLjxcL3A+XHJcblxyXG48cD5cdWIwOThcdWIyOTQmbmJzcDtcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkMGQwXHVjODE1XHVjNzQ0IFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM1YmJcdWM3NDAgXHVhY2JkXHVkNWQ4XHVjNzNjXHViODVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3N2NcdWM3M2NcdWQwYTRcdWIyOTQmbmJzcDtcdWMwYWNcdWFjNzRcdWM3NTggXHVjNzc4XHVhY2ZjXHVhZDAwXHVhY2M0XHViOTdjIFx1YWMwNFx1YjJlOFx1ZDU1OFx1YWM4YyBcdWM1NTVcdWNkOTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YzViNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWMwYWNcdWFjNzQgQVx1YWMwMCBcdWM3N2NcdWM1YjRcdWIwYWNcdWIyZTRcdWJhNzQgXHViYjM0XHVjODcwXHVhYzc0IFx1YzBhY1x1YWM3NCBCXHVhYzAwIFx1Yzc3Y1x1YzViNFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWM1YjQuIFx1Yzc3NFx1YjdmMCBcdWFkMDBcdWFjYzRcdWI5N2MgQSAmcmFycjsgQlx1Yjc3Y1x1YWNlMCBcdWIwOThcdWQwYzBcdWIwYjRcdWM3OTAuIFx1YzBhY1x1YWM3NFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWMgXHVjNzc0XHVjNWI0XHVjODM4XHVjMTFjIEEgJnJhcnI7IEIgJnJhcnI7IENcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzViNCwgXHVkNTU4XHVjOWMwXHViOWNjIEEgJnJhcnI7IEIgJnJhcnI7IEMgJnJhcnI7IC4uLiAmcmFycjsgQSBcdWFjMTlcdWM3NDBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMjFjXHVkNjU4XHVkNTU4XHViMjk0IFx1YWQwMFx1YWNjNFx1YjI5NCBcdWM1YzZcdWM1YjQuIFx1YWRmOFx1YjlhY1x1YWNlMCZuYnNwO1x1YjljY1x1YzU3ZCBBICZyYXJyOyBDXHVjNzc0XHVhY2UwIEIgJnJhcnI7IENcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwIFx1YzBhY1x1YWM3NCZuYnNwO0NcdWFjMDAgXHVjNzdjXHVjNWI0XHViMGFjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjNzQmbmJzcDtBXHViMDk4IFx1YzBhY1x1YWM3NCZuYnNwO0JcdWM5MTEgXHVkNTU4XHViMDk4XHViMjk0Jm5ic3A7XHVjNzdjXHVjNWI0XHViMGFjXHVjNzQ0XHVhYzcwXHViNzdjXHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YzViNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHViM2M0IFx1YzYyNFx1YjI5OFx1Yzc1OCBcdWMwYjRcdWM3NzggXHVjMGFjXHVhYzc0XHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjBhY1x1YWQ3MC4gXHVjOWMwXHVhZTA4IFx1Yzk5ZFx1YWM3MFx1YjRlNFx1Yzc0NCBcdWMyMThcdWM5ZDFcdWQ1ODhcdWM1YjQsIFx1Yzc3NFx1YWM3OFx1Yjg1YyBcdWIwOThcdWIyOTQgXHVjZDFkJm5ic3A7Tlx1YWMxY1x1Yzc1OCBcdWMwYWNcdWFjNzRcdWM3NzQgXHVjNzdjXHVjNWI0XHViMGFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YzViNC4gXHVjNzc0XHVhYzgzXHVjNzNjXHViODVjIFx1YjA5OFx1YjI5NCZuYnNwO1x1YmIzNFx1Yzg3MFx1YWM3NCBcdWM3N2NcdWM1YjRcdWIwYWNcdWM3NDQmbmJzcDtcdWIyZTRcdWI5NzggXHVjMGFjXHVhYzc0XHViNGU0XHVjNzc0IFx1YjM1NCZuYnNwO1x1Yzc4OFx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhYzhjIFx1YjQxOFx1YzVjOFx1YzViNC4gXHViMDk4XHViMjk0IFx1YzljMFx1YzEzMVx1YWNmYyBcdWFjYmRcdWQ1ZDhcdWM3NDQgXHViYWE4XHViNDUwIFx1YWNiOFx1YmU0NFx1ZDU1YyBcdWQwZDBcdWM4MTVcdWM3NzRcdWIyYzhcdWFlNGMuJm5ic3A7XHViMmY5XHVjMmUwXHViM2M0IFx1YWNmY1x1YzVmMCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVjNzdjXHVjNWI0XHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzc0XHVjNzU4IFx1YWMxY1x1YzIxOCBEJm5ic3A7KDEgJmxlOyBEICZsZTsgMTAwMCksIFx1YzBhY1x1YWM3NFx1YjRlNCBcdWFjMDRcdWM3NTggXHVhZDAwXHVhY2M0XHVjNzU4IFx1YWMxY1x1YzIxOCZuYnNwO00mbmJzcDsoMSAmbGU7IE0gJmxlOyAxMDAwMDApLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNzdjXHVjNWI0XHViMDljIFx1YzBhY1x1YWM3NFx1Yzc1OCBcdWFjMWNcdWMyMTgmbmJzcDtOICgxICZsZTsgTiAmbGU7IEQpXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBBXHVjNjQwIEIoMSAmbGU7IEEsIEIgJmxlOyBEKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IFx1YzBhY1x1YWM3NCZuYnNwO0EsQlx1YWMwMCZuYnNwOyZuYnNwO0EgJnJhcnI7IEJcdWM3NzggXHVhZDAwXHVhY2M0XHVjNWQwIFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzdjXHVjNWI0XHViMDljIFx1YzBhY1x1YWM3NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4Jm5ic3A7WCAoMSAmbGU7IFggJmxlOyBEKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM0XHVjODcwXHVhYzc0IFx1Yzc3Y1x1YzViNFx1YjA5OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMGFjXHVhYzc0XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjMjFjXHVjMTFjXHViMjk0IFx1YzBjMVx1YWQwMFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+XHVjMGFjXHVhYzc0IDRcdWFjMDAgXHVjNzdjXHVjNWI0XHViMGFjXHViMjk0XHViMzcwLCBcdWMwYWNcdWFjNzQmbmJzcDt7MiwzfVx1YzkxMVx1YzVkMCBcdWM1YjRcdWI1YTQgXHVjMGFjXHVhYzc0XHVjNzc0IDRcdWI5N2MgXHVjNzdjXHVjNzNjXHVjZjMwXHViMjk0XHVjOWMwIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjMGFjXHVhYzc0Jm5ic3A7ezIsM31cdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWMwYWNcdWFjNzQgMVx1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjLCBcdWQ2NGRcdWM5ODhcdWIyOTQgXHVjNWI0XHVjYTBjXHViNGUwIFx1YzBhY1x1YWM3NCAxXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjBhY1x1YzViNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM3NzRcdWI4NWMgXHVjNzc4XHVkNTc0XHVjMTFjIFx1YzBhY1x1YWM3NCZuYnNwOzIsMyw0XHViM2M0IFx1Yzc3Y1x1YzViNFx1YjBhY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI4OTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIT0xNRVMiLCJkZXNjcmlwdGlvbiI6IjxwPlNoZXJsb2NrIEhvbG1lcyBpcyBhIHJlbm93bmVkIGRldGVjdGl2ZS4gSGlzIFNjb3RsYW5kIFlhcmQgY29sbGVhZ3VlcyBvZnRlbiBwcm92aWRlIGhpbSB3aXRoIGEgc2V0IG9mIGV2aWRlbmNlIGFuZCBhc2sgZm9yIGhpcyBoZWxwIGluIHNvbHZpbmcgdGhlIG15c3Rlcmllcy4gQWZ0ZXIgbWFueSB5ZWFycyBvZiBwcmFjdGljZSwgSG9sbWVzIGhhcyBnYWluZWQgYW4gZW5vcm1vdXMgYW1vdW50IG9mIGV4cGVyaWVuY2UgYW5kIGFscmVhZHkga25vd3MgY2F1c2VzIGZvciBtYW55IGNvbW1vbiBldmVudHMsIHdoaWNoLCBjb21iaW5lZCB3aXRoIGhpcyBleHRyYW9yZGluYXJ5IGRlZHVjdGl2ZSBjYXBhYmlsaXRpZXMsIGVuYWJsZXMgaGltIHRvIHNvbHZlIGNhc2VzIGluIGEgbWF0dGVyIG9mIG1pbnV0ZXMsIGZyb20gdGhlIGNvbWZvcnQgb2YgaGlzIGNoYWlyLjxcL3A+XHJcblxyXG48cD5Ib2xtZXMmIzM5OyBrbm93bGVkZ2UgYmFzZSBjYW4gYmUgbW9kZWxlZCBhcyBhIHNldCBvZiBpbXBsaWNhdGlvbnMgb2YgdGhlIGZvcm0gQSAmcmFycjsgQiAod2hlcmUgQSBhbmQgQiByZXByZXNlbnQgZXZlbnRzKSwgd2hpY2ggbWVhbnMgdGhhdCwgaWYgQSBvY2N1cnJlZCwgZXZlbnQgQiBtdXN0IGhhdmUgYWxzbyBvY2N1cnJlZCAocmVtZW1iZXIgdGhhdCBsb2dpY2FsIGltcGxpY2F0aW9uIGlzIGZhbHNlIG9ubHkgaWYgQSBpcyB0cnVlIGFuZCBCIGlzIGZhbHNlKS4gT2YgY291cnNlLCBpbXBsaWNhdGlvbnMgY2FuIGZvcm0gY2hhaW5zIG9mIHJlYXNvbmluZywgZS5nLiBBICZyYXJyOyBCICZyYXJyOyBDLiBIb3dldmVyLCB0aGVyZSB3aWxsIG5ldmVyIGJlIGEgY2lyY3VsYXIgY2hhaW4gb2YgaW1wbGljYXRpb25zIChlLmcuIEEgJnJhcnI7IEIgJnJhcnI7IEMgJnJhcnI7IC4uLiAmcmFycjsgQSkuPFwvcD5cclxuXHJcbjxwPkhvbG1lcyBpcyBnaXZlbiBhIHNldCBTID0ge1M8c3ViPjE8XC9zdWI+LCBTPHN1Yj4yPFwvc3ViPiwgUzxzdWI+MzxcL3N1Yj4sIC4uLiwgUzxzdWI+bjxcL3N1Yj59IG9mIGV2ZW50cyB0aGF0IGFyZSBrbm93biB0byBoYXZlIG9jY3VycmVkLiBIZSBjYW4gdGhlbiwgdXNpbmcgaGlzIGV4dGVuc2l2ZSBrbm93bGVkZ2UgYW5kIGRlZHVjdGl2ZSBwb3dlcnMsIGZpbmQgYWxsIGV2ZW50cyB0aGF0IGhhdmUgY2VydGFpbmx5IG9jY3VycmVkLjxcL3A+XHJcblxyXG48cD5JdCYjMzk7cyBpbXBvcnRhbnQgdG8gbm90ZSB0aGF0IEhvbG1lcyYjMzk7IGtub3dsZWRnZSBpcyBzbyBtaW5kLWJvZ2dsaW5nbHkgaHVnZSB0aGF0IGhlIGtub3dzIGFsbCBwb3NzaWJsZSBjYXVzZXMgb2YgZXZlbnRzLiBJbiBvdGhlciB3b3JkcywgdGhlcmUgaXMgbm8gaW1wbGljYXRpb24gdGhhdCBpcyB0cnVlLCBidXQgbm90IGluY2x1ZGVkIGluIEhvbG1lcyYjMzk7IGtub3dsZWRnZSBiYXNlLjxcL3A+XHJcblxyXG48cD5NYW55IGRldGVjdGl2ZSBhZ2VuY2llcyB3b3VsZCBoaWdobHkgYXBwcmVjaWF0ZSBIb2xtZXMmIzM5OyBvbmUgb2YgYSBraW5kIGNhcGFiaWxpdGllcywgc28geW91IHdlcmUgZ2l2ZW4gYSB0YXNrIHRvIGFjY29tcGxpc2ggd2l0aCBhIGNvbXB1dGVyIHdoYXQgaXMgb3V0IG9mIHJlYWNoIGZvciBvcmRpbmFyeSBtb3J0YWxzLiBXcml0ZSBhIHByb2dyYW0gdG8gZmluZCBhbGwgZXZlbnRzIHRoYXQgaGF2ZSBjZXJ0YWlubHkgb2NjdXJyZWQgYmFzZWQgb24gdGhlIGdpdmVuIGltcGxpY2F0aW9ucyBhbmQgZXZpZGVuY2UgY29sbGVjdGVkIGJ5IHlvdXIgY29sbGVhZ3VlIGRldGVjdGl2ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnNpc3RzIG9mIHRocmVlIGludGVnZXJzLCBEICgxICZsZTsgRCAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB0eXBlcyBvZiBldmVudHMsIE0gKDEgJmxlOyBNICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiBpbXBsaWNhdGlvbnMsIGFuZCBOICgxICZsZTsgTiAmbGU7IEQpLCB0aGUgbnVtYmVyIG9mIGV2aWRlbmNlIGNvbGxlY3RlZCBieSB0aGUgZGV0ZWN0aXZlcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgTSBsaW5lcyB0aGF0IGZvbGxvdyBjb250YWlucyB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyBEKSwgZGVzY3JpYmluZyBhbiBpbXBsaWNhdGlvbiBBICZyYXJyOyBCLjxcL3A+XHJcblxyXG48cD5GaW5hbGx5LCBlYWNoIG9mIHRoZSBsYXN0IE4gbGluZXMgY29udGFpbiBhbiBpbnRlZ2VyIFggKDEgJmxlOyBYICZsZTsgRCkgZGVzY3JpYmluZyBhbiBldmVudCB0aGF0IG11c3QgaGF2ZSBvY2N1cnJlZCwgYmFzZWQgb24gdGhlIGV2aWRlbmNlIGNvbGxlY3RlZCBieSBkZXRlY3RpdmVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBpbnRlZ2VycyAoaW4gYW55IG9yZGVyKSByZXByZXNlbnRpbmcgZXZlbnRzIHRoYXQgaGF2ZSBjZXJ0YWlubHkgb2NjdXJyZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+VGhlIGtub3dsZWRnZSBiYXNlIGNvbnRhaW5zIGltcGxpY2F0aW9ucyAxIC0mZ3Q7IDMgYW5kIDIgLSZndDsgMy4gVGhlcmVmb3JlLCBIb2xtZXMga25vd3MgdGhhdCBldmVudCAzIGNhbiBiZSBjYXVzZWQgb25seSBieSBldmVudHMgMSBhbmQgMiwgYnV0ICh3aXRob3V0IGFueSBleHRyYSBpbmZvcm1hdGlvbiksIGhlIGNhbiYjMzk7dCBiZSBjZXJ0YWluIHdoaWNoIG9uZSBvZiB0aG9zZSBldmVudHMgYWN0dWFsbHkgY2F1c2VkIDMuIEFzIGEgcmVzdWx0LCBvbmx5IGV2ZW50IHRoYXQgbXVzdCBoYXZlIG9jY3VycmVkIGlzIHRoZSBvbmUgZ2l2ZW4gaW4gdGhlIGlucHV0LjxzcGFuIHN0eWxlPVwiZGlzcGxheTogbm9uZTtcIj4mbmJzcDs8XC9zcGFuPjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD5Ib2xtZXMgZG9lc24mIzM5O3Qga25vdyB3aGljaCBldmVudCBmcm9tIHRoZSBzZXQgezIsIDN9IGlzIGRpcmVjdGx5IHJlc3BvbnNpYmxlIGZvciBldmVudCA0LiBIb3dldmVyLCBhcyBib3RoIG9mIHRob3NlIGV2ZW50cyBhcmUgY2F1c2VkIG9ubHkgYnkgZXZlbnQgMSwgSG9sbWVzIGNhbiBkZWR1Y2UgdGhhdCBldmVudCAxIG11c3QgaGF2ZSBvY2N1cnJlZC4gQXMgYSBjb25zZXF1ZW5jZSwgZXZlbnRzIDIsIDMgYW5kIDQgKGdpdmVuIGJ5IHRoZSBkZXRlY3RpdmVzKSBoYXZlIGFsc28gb2NjdXJyZWQuPFwvcD5cclxuIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #6 5번