시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 763 274 222 36.634%

문제

지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳, 바다와 만나는 곳이다.

네모 안의 숫자는 순서를 나타내고, 동그라미 안의 숫자는 노드 번호를 나타낸다.

하천계의 Strahler 순서는 다음과 같이 구할 수 있다.

  • 강의 근원인 노드의 순서는 1이다.
  • 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.

하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드는 항상 1개이며, 위의 그림의 Strahler 순서는 3이다.

하천계의 정보가 주어졌을 때, Strahler 순서를 구하는 프로그램을 작성하시오.

실제 강 중에서 Strahler 순서가 가장 큰 강은 아마존 강(12)이며, 미국에서 가장 큰 값을 갖는 강은 미시시피 강(10)이다.

노드 M은 항상 바다와 만나는 노드이다.

입력

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1000)가 주어진다.

각 테스트 케이스의 첫째 줄에는 K, M, P가 주어진다. K는 테스트 케이스 번호, M은 노드의 수, P는 간선의 수이다. (2 ≤ M ≤ 1000) 다음 P개 줄에는 간선의 정보를 나타내는 A, B가 주어지며, A에서 B로 물이 흐른다는 뜻이다. (1 ≤ A, B ≤ M) M은 항상 바다와 만나는 노드이며, 밖으로 향하는 간선은 존재하지 않는다.

출력

각 테스트 케이스마다 테스트 케이스 번호와 입력으로 주어진 하천계의 Strahler 순서를 출력한다.

예제 입력 1

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

예제 출력 1

1 3
W3sicHJvYmxlbV9pZCI6Ijk0NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJTdHJhaGxlciBcdWMyMWNcdWMxMWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMFx1YzljOFx1ZDU1OVx1YzVkMFx1YzExYyBcdWQ1NThcdWNjOWNcdWFjYzRcdWIyOTQgXHVjNzIwXHVkNWE1XHVhZGY4XHViNzk4XHVkNTA0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMTVcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHViYjNjXHVjNzc0IFx1ZDc1MFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWQ2MzhcdWMyMThcdWIwOTggXHVjMGQ4XHVjYzk4XHViN2ZjIFx1YWMxNVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhY2YzLCBcdWFjMTVcdWM3NzQgXHVkNTY5XHVjY2QwXHVjOWMwXHVhYzcwXHViMDk4IFx1YjA5OFx1YjIwNFx1YzViNFx1YzljMFx1YjI5NCBcdWFjZjMsIFx1YmMxNFx1YjJlNFx1YzY0MCBcdWI5Y2NcdWIwOThcdWIyOTQgXHVhY2YzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N0cmFobGVyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI5OXB4OyB3aWR0aDozNTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIxMjRcdWJhYTggXHVjNTQ4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWIzZDlcdWFkZjhcdWI3N2NcdWJiZjggXHVjNTQ4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIxNzhcdWI0ZGMgXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjYzljXHVhY2M0XHVjNzU4IFN0cmFobGVyIFx1YzIxY1x1YzExY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWMxNVx1Yzc1OCBcdWFkZmNcdWM2ZDBcdWM3NzggXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIwOThcdWJhMzhcdWM5YzAgXHViMTc4XHViNGRjXHViMjk0IFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YWMxNVx1Yzc1OCBcdWMyMWNcdWMxMWMgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IGlcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjMTUgXHVjOTExXHVjNWQwXHVjMTFjIFN0cmFobGVyIFx1YzIxY1x1YzExY1x1YWMwMCBpXHVjNzc4IFx1YWMxNVx1Yzc3NCZuYnNwOzFcdWFjMWNcdWM3NzRcdWJhNzQgXHVjMjFjXHVjMTFjXHViMjk0IGksIDJcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc0XHViYTc0IFx1YzIxY1x1YzExY1x1YjI5NCBpKzFcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTU4XHVjYzljXHVhY2M0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWJjMTRcdWIyZTRcdWM2NDAgXHViOWNjXHViMDk4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVhYzE5XHViMmU0LiBcdWJjMTRcdWIyZTRcdWM2NDAgXHViOWNjXHViMDk4XHViMjk0IFx1YjE3OFx1YjRkY1x1YjI5NCBcdWQ1NmRcdWMwYzEgMVx1YWMxY1x1Yzc3NFx1YmE3MCwgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc1OCBTdHJhaGxlciBcdWMyMWNcdWMxMWNcdWIyOTQgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjYzljXHVhY2M0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBTdHJhaGxlciBcdWMyMWNcdWMxMWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzJlNFx1YzgxYyBcdWFjMTUgXHVjOTExXHVjNWQwXHVjMTFjIFN0cmFobGVyIFx1YzIxY1x1YzExY1x1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxNVx1Yzc0MCZuYnNwO1x1YzU0NFx1YjljOFx1Yzg3NCBcdWFjMTUoMTIpXHVjNzc0XHViYTcwLCBcdWJiZjhcdWFkNmRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0IFx1YWMxNVx1Yzc0MCBcdWJiZjhcdWMyZGNcdWMyZGNcdWQ1M2MgXHVhYzE1KDEwKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTc4XHViNGRjIE1cdWM3NDAgXHVkNTZkXHVjMGMxIFx1YmMxNFx1YjJlNFx1YzY0MCBcdWI5Y2NcdWIwOThcdWIyOTQgXHViMTc4XHViNGRjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBLLCBNLCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gS1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCwgTVx1Yzc0MCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjMjE4LCBQXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuICgyICZsZTsgTSAmbGU7IDEwMDApIFx1YjJlNFx1Yzc0YyBQXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YmIzY1x1Yzc3NCBcdWQ3NTBcdWI5NzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBNKSBNXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWJjMTRcdWIyZTRcdWM2NDAgXHViOWNjXHViMDk4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc3NFx1YmE3MCwgXHViYzE2XHVjNzNjXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU1OFx1Y2M5Y1x1YWNjNFx1Yzc1OCBTdHJhaGxlciBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdHJhaGxlciBPcmRlciIsImRlc2NyaXB0aW9uIjoiPHA+SW4gZ2VvbG9neSwgYSByaXZlciBzeXN0ZW0gY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgZGlyZWN0ZWQgZ3JhcGguIEVhY2ggcml2ZXIgc2VnbWVudCBpcyBhbiBlZGdlO3dpdGggdGhlIGVkZ2UgcG9pbnRpbmcgdGhlIHNhbWUgd2F5IHRoZSB3YXRlciBmbG93cy4gTm9kZXMgYXJlIGVpdGhlciB0aGUgc291cmNlIG9mIGEgcml2ZXIgc2VnbWVudChmb3IgZXhhbXBsZSwgYSBsYWtlIG9yIHNwcmluZyksIHdoZXJlIHJpdmVyIHNlZ21lbnRzIG1lcmdlIG9yIGRpdmVyZ2UsIG9yIHRoZSBtb3V0aCBvZiB0aGUgcml2ZXI8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdHJhaGxlci5wbmdcIiBzdHlsZT1cImhlaWdodDoyOTlweDsgd2lkdGg6MzU0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIG51bWJlciBpbiBhIGJveCBpcyB0aGUgb3JkZXIuIFRoZSBudW1iZXIgaW4gYSBjaXJjbGUgaXMgdGhlIG5vZGUgbnVtYmVyLjxcL3A+XHJcblxyXG48cD5UaGUgU3RyYWhsZXIgb3JkZXIgb2YgYSByaXZlciBzeXN0ZW0gaXMgY29tcHV0ZWQgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgb3JkZXIgb2YgZWFjaCBzb3VyY2Ugbm9kZSBpcyAxLjxcL2xpPlxyXG5cdDxsaT5Gb3IgZXZlcnkgb3RoZXIgbm9kZSwgbGV0IGkgYmUgdGhlIGhpZ2hlc3Qgb3JkZXIgb2YgYWxsIGl0cyB1cHN0cmVhbSBub2Rlcy4gSWYganVzdCBvbmUgdXBzdHJlYW1ub2RlIGhhcyBvcmRlciBpLCB0aGVuIHRoaXMgbm9kZSBhbHNvIGhhcyBvcmRlciBpLiBJZiB0d28gb3IgbW9yZSB1cHN0cmVhbSBub2RlcyBoYXZlIG9yZGVyaSwgdGhlbiB0aGlzIG5vZGUgaGFzIG9yZGVyIGkrMS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgb3JkZXIgb2YgdGhlIGVudGlyZSByaXZlciBzeXN0ZW0gaXMgdGhlIG9yZGVyIG9mIHRoZSBtb3V0aCBub2RlLiBJbiB0aGlzIHByb2JsZW0sIHRoZSByaXZlciBzeXN0ZW13aWxsIGhhdmUganVzdCBvbmUgbW91dGguIEluIHRoZSBwaWN0dXJlIGFib3ZlLCB0aGUgU3RyYWhsZXIgb3JkZXIgaXMgdGhyZWUgKDMpLjxcL3A+XHJcblxyXG48cD5Zb3UgbXVzdCB3cml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBvcmRlciBvZiBhIGdpdmVuIHJpdmVyIHN5c3RlbS48XC9wPlxyXG5cclxuPHA+VGhlIGFjdHVhbCByaXZlciB3aXRoIHRoZSBoaWdoZXN0IG9yZGVyIGlzIHRoZSBBbWF6b24sIHdpdGggb3JkZXIgMTIuIFRoZSBoaWdoZXN0IGluIHRoZSBVLlMuIGlzIHRoZU1pc3Npc3NpcHBpLCB3aXRoIG9yZGVyIDEwLjxcL3A+XHJcblxyXG48cD5Ob2RlIE0gaXMgdGhlIG1vdXRoIG9mIHRoZSByaXZlci4gSXQgaGFzIG5vIG91dGdvaW5nIGVkZ2VzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBLLCAoMSAmbGU7IEsgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHN0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGxpbmVzIG9mIGlucHV0LiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIGRhdGEgc2V0IGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlaW50ZWdlcnMsIEssIE0gYW5kIFAgKDIgJmxlOyBNICZsZTsgMTAwMCkuIEsgaXMgdGhlIGRhdGEgc2V0IG51bWJlci4gTSBpcyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIHRoZWdyYXBoIGFuZCBQIGlzIHRoZSBudW1iZXIgb2YgZWRnZXMuIFRoZSBmaXJzdCBsaW5lIGlzIGZvbGxvd2VkIGJ5IFAgbGluZXMsIGVhY2ggZGVzY3JpYmluZyBhbiBlZGdlIG9mdGhlIGdyYXBoLiBUaGUgbGluZSB3aWxsIGNvbnRhaW4gdHdvIHBvc2l0aXZlIGludGVnZXJzLCBBIGFuZCBCLCBpbmRpY2F0aW5nIHRoYXQgd2F0ZXIgZmxvd3MgZnJvbSBub2RlIEF0byBub2RlIEIgKDEgJmxlOyBBLCBCICZsZTsgTSkuIE5vZGUgTSBpcyB0aGUgbW91dGggb2YgdGhlIHJpdmVyLiBJdCBoYXMgbm8gb3V0Z29pbmcgZWRnZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQuIFRoZSBsaW5lIGNvbnNpc3RzIG9mIHRoZSBkYXRhIHNldCBudW1iZXIsIGEgc2luZ2xlc3BhY2UgYW5kIHRoZSBvcmRlciBvZiB0aGUgcml2ZXIgc3lzdGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest C번