시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 668 97 77 20.533%

문제

트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. 이때, 노드 u에서 노드 v로 가는 간선이 존재하면 간선을 u에 대해서는 '나가는 간선', v에 대해서는 '들어오는 간선'이라고 하자.

  1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
  2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
  3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

아래의 그림을 보자. 원은 노드, 화살표는 간선을 의미하며, 화살표의 방향이 노드 u에서 노드 v로 향하는 경우 이는 이 간선이 u에서 나가는 간선이며 v로 들어오는 간선이다. 3개의 그림 중 앞의 2개는 트리지만 뒤의 1개는 트리가 아니다.

당신은 간선의 정보들을 받아서 해당 케이스가 트리인지를 판별해야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 입력의 끝에는 두 개의 음의 정수가 주어진다.

각 테스트 케이스는 여러 개의 정수쌍으로 이루어져 있으며, 테스트 케이스의 끝에는 두 개의 0이 주어진다.

각 정수쌍 u, v에 대해서 이는 노드 u에서 노드 v로 가는 간선이 존재함을 의미한다. u와 v는 0보다 크다.

출력

각 테스트 케이스에 대해서, 테스트 케이스의 번호가 k일 때(k는 1부터 시작하며, 1씩 증가한다) 트리일 경우 "Case k is a tree."를, 트리가 아닐 경우 "Case k is not a tree."를 출력한다.

예제 입력 1

6 8  5 3  5 2  6 4
5 6  0 0

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

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1

예제 출력 1

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
W3sicHJvYmxlbV9pZCI6IjY0MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NzhcdWFjMDA/IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI5YWNcdWIyOTQgXHVhZDQ5XHVjN2E1XHVkNzg4IFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjNzkwXHViOGNjIFx1YWQ2Y1x1Yzg3MFx1Yzc3NFx1YjJlNC4gXHVkMmI4XHViOWFjXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3OTBcdWI4Y2MgXHVhZDZjXHVjODcwXHViMjk0IFx1YmU0NFx1YzViNCBcdWM3ODhcdWFjNzBcdWIwOTgoXHViMTc4XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAwXHVhYzFjKSwgXHViMTc4XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAxXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCBcdWJjMjlcdWQ1YTUgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjE3OFx1YjRkYyB1XHVjNWQwXHVjMTFjIFx1YjE3OFx1YjRkYyB2XHViODVjIFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0IFx1YWMwNFx1YzEyMFx1Yzc0NCB1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCAmIzM5O1x1YjA5OFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjAmIzM5Oywgdlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgJiMzOTtcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhYzA0XHVjMTIwJiMzOTtcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVkNTU4XHViMDk4XHViM2M0IFx1YzVjNlx1YjI5NCBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1YjE3OFx1YjRkY1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWI4ZThcdWQyYjgocm9vdCkgXHViMTc4XHViNGRjXHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOGU4XHVkMmI4IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVhYzAwXHViMmE1XHVkNTU4XHViYTcwLCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVjMTMxXHViOWJkXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM1NDRcdWI3OThcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQ0IFx1YmNmNFx1Yzc5MC4gXHVjNmQwXHVjNzQwIFx1YjE3OFx1YjRkYywgXHVkNjU0XHVjMGI0XHVkNDVjXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWJhNzAsIFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM3NzQmbmJzcDtcdWIxNzhcdWI0ZGMmbmJzcDt1XHVjNWQwXHVjMTFjIFx1YjE3OFx1YjRkYyB2XHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFjMDRcdWMxMjBcdWM3NzQgdVx1YzVkMFx1YzExYyBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0XHViYTcwIHZcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NFx1YjJlNC4gM1x1YWMxY1x1Yzc1OCBcdWFkZjhcdWI5YmMgXHVjOTExJm5ic3A7XHVjNTVlXHVjNzU4IDJcdWFjMWNcdWIyOTQgXHVkMmI4XHViOWFjXHVjOWMwXHViOWNjIFx1YjRhNFx1Yzc1OCAxXHVhYzFjXHViMjk0IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3RyZWUxLmdpZlwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3RyZWUyLmdpZlwiIHN0eWxlPVwiYmFja2dyb3VuZC1jb2xvcjppbml0aWFsOyBmb250LXNpemU6bWVkaXVtOyBoZWlnaHQ6MjEwcHg7IHdpZHRoOjIwNHB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvdHJlZTMuZ2lmXCIgc3R5bGU9XCJiYWNrZ3JvdW5kLWNvbG9yOmluaXRpYWw7IGZvbnQtc2l6ZTptZWRpdW07IGhlaWdodDoxOTRweDsgd2lkdGg6MTY0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI0ZTRcdWM3NDQgXHViYzFiXHVjNTQ0XHVjMTFjIFx1ZDU3NFx1YjJmOSBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVkMmI4XHViOWFjXHVjNzc4XHVjOWMwXHViOTdjIFx1ZDMxMFx1YmNjNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM3NGNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWMzMGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzgxNVx1YzIxOFx1YzMwZCB1LCB2XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3NzRcdWIyOTQgXHViMTc4XHViNGRjIHVcdWM1ZDBcdWMxMWMgXHViMTc4XHViNGRjIHZcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjhcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiB1XHVjNjQwIHZcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBrXHVjNzdjIFx1YjU0YyhrXHViMjk0IDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCAxXHVjNTI5IFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNCkmbmJzcDtcdWQyYjhcdWI5YWNcdWM3N2MgXHVhY2JkXHVjNmIwJm5ic3A7JnF1b3Q7Q2FzZSBrIGlzIGEgdHJlZS4mcXVvdDtcdWI5N2MsIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM1NDRcdWIyZDAgXHVhY2JkXHVjNmIwICZxdW90O0Nhc2UgayBpcyBub3QgYSB0cmVlLiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjQxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklzIEl0IEEgVHJlZT8iLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJlZSBpcyBhIHdlbGwta25vd24gZGF0YSBzdHJ1Y3R1cmUgdGhhdCBpcyBlaXRoZXIgZW1wdHkgKG51bGwsIHZvaWQsIG5vdGhpbmcpIG9yIGlzIGEgc2V0IG9mIG9uZSBvciBtb3JlIG5vZGVzIGNvbm5lY3RlZCBieSBkaXJlY3RlZCBlZGdlcyBiZXR3ZWVuIG5vZGVzIHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZyBwcm9wZXJ0aWVzLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZXJlIGlzIGV4YWN0bHkgb25lIG5vZGUsIGNhbGxlZCB0aGUgcm9vdCwgdG8gd2hpY2ggbm8gZGlyZWN0ZWQgZWRnZXMgcG9pbnQuPFwvbGk+XHJcblx0PGxpPkV2ZXJ5IG5vZGUgZXhjZXB0IHRoZSByb290IGhhcyBleGFjdGx5IG9uZSBlZGdlIHBvaW50aW5nIHRvIGl0LjxcL2xpPlxyXG5cdDxsaT5UaGVyZSBpcyBhIHVuaXF1ZSBzZXF1ZW5jZSBvZiBkaXJlY3RlZCBlZGdlcyBmcm9tIHRoZSByb290IHRvIGVhY2ggbm9kZS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIGlsbHVzdHJhdGlvbnMgYmVsb3csIGluIHdoaWNoIG5vZGVzIGFyZSByZXByZXNlbnRlZCBieSBjaXJjbGVzIGFuZCBlZGdlcyBhcmUgcmVwcmVzZW50ZWQgYnkgbGluZXMgd2l0aCBhcnJvd2hlYWRzLiBUaGUgZmlyc3QgdHdvIG9mIHRoZXNlIGFyZSB0cmVlcywgYnV0IHRoZSBsYXN0IGlzIG5vdC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvdHJlZTEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTk4cHg7IHdpZHRoOjE2OHB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvdHJlZTIuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MjEwcHg7IHdpZHRoOjIwNHB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvdHJlZTMuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTk0cHg7IHdpZHRoOjE2NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSB5b3Ugd2lsbCBiZSBnaXZlbiBzZXZlcmFsIGRlc2NyaXB0aW9ucyBvZiBjb2xsZWN0aW9ucyBvZiBub2RlcyBjb25uZWN0ZWQgYnkgZGlyZWN0ZWQgZWRnZXMuIEZvciBlYWNoIG9mIHRoZXNlIHlvdSBhcmUgdG8gZGV0ZXJtaW5lIGlmIHRoZSBjb2xsZWN0aW9uIHNhdGlzZmllcyB0aGUgZGVmaW5pdGlvbiBvZiBhIHRyZWUgb3Igbm90LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgY29uc2lzdCBvZiBhIHNlcXVlbmNlIG9mIGRlc2NyaXB0aW9ucyAodGVzdCBjYXNlcykgZm9sbG93ZWQgYnkgYSBwYWlyIG9mIG5lZ2F0aXZlIGludGVnZXJzLiBFYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBlZGdlIGRlc2NyaXB0aW9ucyBmb2xsb3dlZCBieSBhIHBhaXIgb2YgemVyb2VzIEVhY2ggZWRnZSBkZXNjcmlwdGlvbiB3aWxsIGNvbnNpc3Qgb2YgYSBwYWlyIG9mIGludGVnZXJzOyB0aGUgZmlyc3QgaW50ZWdlciBpZGVudGlmaWVzIHRoZSBub2RlIGZyb20gd2hpY2ggdGhlIGVkZ2UgYmVnaW5zLCBhbmQgdGhlIHNlY29uZCBpbnRlZ2VyIGlkZW50aWZpZXMgdGhlIG5vZGUgdG8gd2hpY2ggdGhlIGVkZ2UgaXMgZGlyZWN0ZWQuIE5vZGUgbnVtYmVycyB3aWxsIGFsd2F5cyBiZSBncmVhdGVyIHRoYW4gemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgZGlzcGxheSB0aGUgbGluZSAmcXVvdDtDYXNlIGsgaXMgYSB0cmVlLiZxdW90OyBvciB0aGUgbGluZSAmcXVvdDtDYXNlIGsgaXMgbm90IGEgdHJlZS4mcXVvdDssIHdoZXJlIGsgY29ycmVzcG9uZHMgdG8gdGhlIHRlc3QgY2FzZSBudW1iZXIgKHRoZXkgYXJlIHNlcXVlbnRpYWxseSBudW1iZXJlZCBzdGFydGluZyB3aXRoIDEpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > North Central North America Regional > NCNA 1997 2번