시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 714 368 280 52.930%

문제

방향 그래프 G = (V, E)가 주어져 있다.

임의의 노드 u, v ∈ V에 대해서 u에서 v로 E에 포함된 간선만을 이용해 갈 수 있는 경로가 있으면 uv로 표현한다.

만약 어떤 노드 vV가 자신으로부터 도달할 수 있는 모든 노드로부터 돌아오는 경로가 있다면, 즉 다음 조건을 만족한다면 노드 vV를 싱크라고 부른다.

  • 조건: ∀wV, (vw) ⇒ (wv)

또한, 그래프 G의 싱크를 모아놓은 집합을 bottom(G)로 표현한다.

  • bottom(G) = {v ∈ V: ∀wV, (vw) ⇒ (wv)}

주어진 그래프 G=(V, E)의 bottom(G)를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫 줄에는 노드의 수 n (1 ≤ n ≤ 5,000)과 음이 아닌 정수 m (1 ≤ m ≤ 100,000)이 주어진다. V = {1, 2, ..., n}이고, 간선의 수 |E|=m임을 의미한다.

그 다음부터는 각 간선을 나타내는 m쌍의 수 v1 w1 v2 w2 ... vm wm이 공백으로 구분되어 주어진다. 이는 (vi, wi) ∈ E를 의미한다.

마지막 줄에 0이 주어지고, 이 경우는 처리하지 않고 프로그램을 종료시켜야 한다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다.

예제 입력 1

3 3
1 3 2 3 3 1
2 1
1 2
0

예제 출력 1

1 3
2

예제 입력 2

2 1
2 1
2 0

5 5
1 2 2 3 3 1 5 4 4 3
5 5
1 2 2 3 3 1 3 4 4 5
5 1
5 1
5 6
1 2 2 3 3 1 3 4 4 5 5 3
0

예제 출력 2

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

힌트

W3sicHJvYmxlbV9pZCI6IjY1NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjMmYxXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMjlcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0Jm5ic3A7PGVtPkc8XC9lbT4gPSAoPGVtPlY8XC9lbT4sIDxlbT5FPFwvZW0+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODRcdWM3NThcdWM3NTggXHViMTc4XHViNGRjIDxlbT51PFwvZW0+LCA8ZW0+djxcL2VtPiZuYnNwOyZpc2luOyA8ZW0+VjxcL2VtPlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgPGVtPnU8XC9lbT5cdWM1ZDBcdWMxMWMgPGVtPnY8XC9lbT5cdWI4NWMgRVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVhYzA0XHVjMTIwXHViOWNjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTc0IDxlbT51PFwvZW0+JnJhcnI7PGVtPnY8XC9lbT5cdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVjNWI0XHViNWE0IFx1YjE3OFx1YjRkYyA8ZW0+djxcL2VtPiAmaXNpbjsgPGVtPlY8XC9lbT5cdWFjMDAgXHVjNzkwXHVjMmUwXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWI4NWNcdWJkODBcdWQxMzAgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1Yzk4OSBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWIxNzhcdWI0ZGMgPGVtPnY8XC9lbT4gJmlzaW47IDxlbT5WPFwvZW0+XHViOTdjIFx1YzJmMVx1ZDA2Y1x1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjODcwXHVhYzc0OiZuYnNwOyZmb3JhbGw7PGVtPnc8XC9lbT4gJmlzaW47IDxlbT5WPFwvZW0+LCAoPGVtPnY8XC9lbT4mcmFycjs8ZW0+dzxcL2VtPikgJnJBcnI7ICg8ZW0+dzxcL2VtPiZyYXJyOzxlbT52PFwvZW0+KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVhZGY4XHViNzk4XHVkNTA0IDxlbT5HPFwvZW0+XHVjNzU4IFx1YzJmMVx1ZDA2Y1x1Yjk3YyBcdWJhYThcdWM1NDRcdWIxOTNcdWM3NDAgXHVjOWQxXHVkNTY5XHVjNzQ0IGJvdHRvbShHKVx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Ym90dG9tKDxlbT5HPFwvZW0+KSA9IHs8ZW0+djxcL2VtPiZuYnNwOyZpc2luOyA8ZW0+VjxcL2VtPjombmJzcDsmZm9yYWxsOzxlbT53PFwvZW0+ICZpc2luOyA8ZW0+VjxcL2VtPiwgKDxlbT52PFwvZW0+JnJhcnI7PGVtPnc8XC9lbT4pICZyQXJyOyAoPGVtPnc8XC9lbT4mcmFycjs8ZW0+djxcL2VtPil9PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNCA8ZW0+RzxcL2VtPj0oPGVtPlY8XC9lbT4sIDxlbT5FPFwvZW0+KVx1Yzc1OCBib3R0b20oPGVtPkc8XC9lbT4pXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjMjE4IDxlbT5uPFwvZW0+ICgxICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1LDAwMClcdWFjZmMgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMTggPGVtPm08XC9lbT4gKDEgJmxlOyBtICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiA8ZW0+VjxcL2VtPiA9IHsxLCAyLCAuLi4sIDxlbT5uPFwvZW0+fVx1Yzc3NFx1YWNlMCwgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOCB8PGVtPkU8XC9lbT58PTxlbT5tPFwvZW0+XHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YmQ4MFx1ZDEzMFx1YjI5NCBcdWFjMDEgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCA8ZW0+bTxcL2VtPlx1YzMwZFx1Yzc1OCBcdWMyMTggPGVtPnY8XC9lbT48c3ViPjE8XC9zdWI+IDxlbT53PFwvZW0+PHN1Yj4xPFwvc3ViPiA8ZW0+djxcL2VtPjxzdWI+MjxcL3N1Yj4gPGVtPnc8XC9lbT48c3ViPjI8XC9zdWI+IC4uLiA8ZW0+djxzdWI+bTxcL3N1Yj48XC9lbT4gPGVtPnc8c3ViPm08XC9zdWI+PFwvZW0+XHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgKDxlbT52PHN1Yj5pPFwvc3ViPjxcL2VtPiwgPGVtPnc8c3ViPmk8XC9zdWI+PFwvZW0+KSZuYnNwOyZpc2luOyA8ZW0+RTxcL2VtPlx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDAgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjYzk4XHViOWFjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjODg1XHViOGNjXHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBib3R0b20oPGVtPkc8XC9lbT4pXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIxNzhcdWI0ZGNcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgYm90dG9tKDxlbT5HPFwvZW0+KVx1YWMwMCBcdWFjZjVcdWM5ZDFcdWQ1NjlcdWM3NzRcdWJhNzQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2JvdHRvbS5naWZcIiBzdHlsZT1cImhlaWdodDoxOTBweDsgd2lkdGg6MTU5cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjY1NDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQm90dG9tIG9mIGEgR3JhcGgiLCJkZXNjcmlwdGlvbiI6IjxwPldlIHdpbGwgdXNlIHRoZSBmb2xsb3dpbmcgKHN0YW5kYXJkKSBkZWZpbml0aW9ucyBmcm9tIGdyYXBoIHRoZW9yeS4gTGV0IDxlbT5WPFwvZW0+IGJlIGEgbm9uZW1wdHkgYW5kIGZpbml0ZSBzZXQsIGl0cyBlbGVtZW50cyBiZWluZyBjYWxsZWQgdmVydGljZXMgKG9yIG5vZGVzKS4gTGV0IDxlbT5FPFwvZW0+IGJlIGEgc3Vic2V0IG9mIHRoZSBDYXJ0ZXNpYW4gcHJvZHVjdCA8ZW0+ViZ0aW1lcztWPFwvZW0+LCBpdHMgZWxlbWVudHMgYmVpbmcgY2FsbGVkIGVkZ2VzLiBUaGVuIDxlbT5HPShWLEUpPFwvZW0+IGlzIGNhbGxlZCBhIGRpcmVjdGVkIGdyYXBoLjxcL3A+XHJcblxyXG48cD5MZXQgPGVtPm48XC9lbT4gYmUgYSBwb3NpdGl2ZSBpbnRlZ2VyLCBhbmQgbGV0IDxlbT5wPShlPHN1Yj4xPFwvc3ViPiwuLi4sZTxzdWI+bjxcL3N1Yj4pPFwvZW0+IGJlIGEgc2VxdWVuY2Ugb2YgbGVuZ3RoIDxlbT5uPFwvZW0+IG9mIGVkZ2VzIDxlbT5lPHN1Yj5pPFwvc3ViPiZpc2luO0U8XC9lbT4gc3VjaCB0aGF0IDxlbT5lPHN1Yj5pPFwvc3ViPj0odjxzdWI+aTxcL3N1Yj4sdjxzdWI+aSsxPFwvc3ViPik8XC9lbT4gZm9yIGEgc2VxdWVuY2Ugb2YgdmVydGljZXMgPGVtPih2PHN1Yj4xPFwvc3ViPiwuLi4sdjxzdWI+bisxPFwvc3ViPik8XC9lbT4uIFRoZW4gPGVtPnA8XC9lbT4gaXMgY2FsbGVkIGEgcGF0aCBmcm9tIHZlcnRleCA8ZW0+djxzdWI+MTxcL3N1Yj48XC9lbT4gdG8gdmVydGV4IDxlbT52PHN1Yj5uKzE8XC9zdWI+PFwvZW0+IGluIDxlbT5HPFwvZW0+IGFuZCB3ZSBzYXkgdGhhdCA8ZW0+djxzdWI+bisxPFwvc3ViPjxcL2VtPiBpcyByZWFjaGFibGUgZnJvbSA8ZW0+djxzdWI+MTxcL3N1Yj48XC9lbT4sIHdyaXRpbmcgPGVtPih2PHN1Yj4xPFwvc3ViPiZyYXJyO3Y8c3ViPm4rMTxcL3N1Yj4pPFwvZW0+LjxcL3A+XHJcblxyXG48cD5IZXJlIGFyZSBzb21lIG5ldyBkZWZpbml0aW9ucy4gQSBub2RlIDxlbT52PFwvZW0+IGluIGEgZ3JhcGggPGVtPkc9KFYsRSk8XC9lbT4gaXMgY2FsbGVkIGEgc2luaywgaWYgZm9yIGV2ZXJ5IG5vZGUgPGVtPnc8XC9lbT4gaW4gPGVtPkc8XC9lbT4gdGhhdCBpcyByZWFjaGFibGUgZnJvbSA8ZW0+djxcL2VtPiwgPGVtPnY8XC9lbT4gaXMgYWxzbyByZWFjaGFibGUgZnJvbSA8ZW0+dzxcL2VtPi4gVGhlIGJvdHRvbSBvZiBhIGdyYXBoIGlzIHRoZSBzdWJzZXQgb2YgYWxsIG5vZGVzIHRoYXQgYXJlIHNpbmtzLCBpLmUuLCA8ZW0+Ym90dG9tKEcpPXt2JmlzaW47VnwmZm9yYWxsO3cmaXNpbjtWOih2JnJhcnI7dykmckFycjsodyZyYXJyO3YpfTxcL2VtPi4gWW91IGhhdmUgdG8gY2FsY3VsYXRlIHRoZSBib3R0b20gb2YgY2VydGFpbiBncmFwaHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLCBlYWNoIG9mIHdoaWNoIGNvcnJlc3BvbmRzIHRvIGEgZGlyZWN0ZWQgZ3JhcGggPGVtPkc8XC9lbT4uIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgbnVtYmVyIDxlbT52PFwvZW0+LCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIDxlbT5HPShWLEUpPFwvZW0+LCB3aGVyZSB0aGUgdmVydGljZXMgd2lsbCBiZSBpZGVudGlmaWVkIGJ5IHRoZSBpbnRlZ2VyIG51bWJlcnMgaW4gdGhlIHNldCA8ZW0+Vj17MSwuLi4sdn08XC9lbT4uIFlvdSBtYXkgYXNzdW1lIHRoYXQgMSAmbGU7IDxlbT52PFwvZW0+ICZsZTsmbmJzcDs1MDAwLCAxICZsZTsgPGVtPmU8XC9lbT4gJmxlOyAxMDAsMDAwLiBUaGF0IGlzIGZvbGxvd2VkIGJ5IGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgPGVtPmU8XC9lbT4gYW5kLCB0aGVyZWFmdGVyLCA8ZW0+ZTxcL2VtPiBwYWlycyBvZiB2ZXJ0ZXggaWRlbnRpZmllcnMgPGVtPnY8c3ViPjE8XC9zdWI+LHc8c3ViPjE8XC9zdWI+LC4uLix2PHN1Yj5lPFwvc3ViPix3PHN1Yj5lPFwvc3ViPjxcL2VtPiB3aXRoIHRoZSBtZWFuaW5nIHRoYXQgPGVtPih2PHN1Yj5pPFwvc3ViPix3PHN1Yj5pPFwvc3ViPikmaXNpbjtFPFwvZW0+LiBUaGVyZSBhcmUgbm8gZWRnZXMgb3RoZXIgdGhhbiBzcGVjaWZpZWQgYnkgdGhlc2UgcGFpcnMuIFRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIHplcm8uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCB0aGUgYm90dG9tIG9mIHRoZSBzcGVjaWZpZWQgZ3JhcGggb24gYSBzaW5nbGUgbGluZS4gVG8gdGhpcyBlbmQsIHByaW50IHRoZSBudW1iZXJzIG9mIGFsbCBub2RlcyB0aGF0IGFyZSBzaW5rcyBpbiBzb3J0ZWQgb3JkZXIgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlIGNoYXJhY3Rlci4gSWYgdGhlIGJvdHRvbSBpcyBlbXB0eSwgcHJpbnQgYW4gZW1wdHkgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvYm90dG9tLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE5MHB4OyB3aWR0aDoxNTlweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2003 B번

  • 문제의 오타를 찾은 사람: kdr06006