시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 573 76 63 18.919%

문제

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

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

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

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

입력

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

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

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

출력

각 테스트 케이스에 대해서, 테스트 케이스의 번호가 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+XHVhYzAxIFx1YzgxNVx1YzIxOFx1YzMwZCB1LCB2XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3NzRcdWIyOTQgXHViMTc4XHViNGRjIHVcdWM1ZDBcdWMxMWMgXHViMTc4XHViNGRjIHZcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjhcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAga1x1Yzc3YyBcdWI1NGMoa1x1YjI5NCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3MCwgMVx1YzUyOSBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQpJm5ic3A7XHVkMmI4XHViOWFjXHVjNzdjIFx1YWNiZFx1YzZiMCZuYnNwOyZxdW90O0Nhc2UgayBpcyBhIHRyZWUuJnF1b3Q7XHViOTdjLCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNTQ0XHViMmQwIFx1YWNiZFx1YzZiMCAmcXVvdDtDYXNlIGsgaXMgbm90IGEgdHJlZS4mcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY0MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJcyBJdCBBIFRyZWU/IiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyZWUgaXMgYSB3ZWxsLWtub3duIGRhdGEgc3RydWN0dXJlIHRoYXQgaXMgZWl0aGVyIGVtcHR5IChudWxsLCB2b2lkLCBub3RoaW5nKSBvciBpcyBhIHNldCBvZiBvbmUgb3IgbW9yZSBub2RlcyBjb25uZWN0ZWQgYnkgZGlyZWN0ZWQgZWRnZXMgYmV0d2VlbiBub2RlcyBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgcHJvcGVydGllcy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGVyZSBpcyBleGFjdGx5IG9uZSBub2RlLCBjYWxsZWQgdGhlIHJvb3QsIHRvIHdoaWNoIG5vIGRpcmVjdGVkIGVkZ2VzIHBvaW50LjxcL2xpPlxyXG5cdDxsaT5FdmVyeSBub2RlIGV4Y2VwdCB0aGUgcm9vdCBoYXMgZXhhY3RseSBvbmUgZWRnZSBwb2ludGluZyB0byBpdC48XC9saT5cclxuXHQ8bGk+VGhlcmUgaXMgYSB1bmlxdWUgc2VxdWVuY2Ugb2YgZGlyZWN0ZWQgZWRnZXMgZnJvbSB0aGUgcm9vdCB0byBlYWNoIG5vZGUuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBpbGx1c3RyYXRpb25zIGJlbG93LCBpbiB3aGljaCBub2RlcyBhcmUgcmVwcmVzZW50ZWQgYnkgY2lyY2xlcyBhbmQgZWRnZXMgYXJlIHJlcHJlc2VudGVkIGJ5IGxpbmVzIHdpdGggYXJyb3doZWFkcy4gVGhlIGZpcnN0IHR3byBvZiB0aGVzZSBhcmUgdHJlZXMsIGJ1dCB0aGUgbGFzdCBpcyBub3QuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3RyZWUxLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE5OHB4OyB3aWR0aDoxNjhweFwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3RyZWUyLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjIxMHB4OyB3aWR0aDoyMDRweFwiIFwvPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3RyZWUzLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE5NHB4OyB3aWR0aDoxNjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0geW91IHdpbGwgYmUgZ2l2ZW4gc2V2ZXJhbCBkZXNjcmlwdGlvbnMgb2YgY29sbGVjdGlvbnMgb2Ygbm9kZXMgY29ubmVjdGVkIGJ5IGRpcmVjdGVkIGVkZ2VzLiBGb3IgZWFjaCBvZiB0aGVzZSB5b3UgYXJlIHRvIGRldGVybWluZSBpZiB0aGUgY29sbGVjdGlvbiBzYXRpc2ZpZXMgdGhlIGRlZmluaXRpb24gb2YgYSB0cmVlIG9yIG5vdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBkZXNjcmlwdGlvbnMgKHRlc3QgY2FzZXMpIGZvbGxvd2VkIGJ5IGEgcGFpciBvZiBuZWdhdGl2ZSBpbnRlZ2Vycy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgZWRnZSBkZXNjcmlwdGlvbnMgZm9sbG93ZWQgYnkgYSBwYWlyIG9mIHplcm9lcyBFYWNoIGVkZ2UgZGVzY3JpcHRpb24gd2lsbCBjb25zaXN0IG9mIGEgcGFpciBvZiBpbnRlZ2VyczsgdGhlIGZpcnN0IGludGVnZXIgaWRlbnRpZmllcyB0aGUgbm9kZSBmcm9tIHdoaWNoIHRoZSBlZGdlIGJlZ2lucywgYW5kIHRoZSBzZWNvbmQgaW50ZWdlciBpZGVudGlmaWVzIHRoZSBub2RlIHRvIHdoaWNoIHRoZSBlZGdlIGlzIGRpcmVjdGVkLiBOb2RlIG51bWJlcnMgd2lsbCBhbHdheXMgYmUgZ3JlYXRlciB0aGFuIHplcm8uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGRpc3BsYXkgdGhlIGxpbmUgJnF1b3Q7Q2FzZSBrIGlzIGEgdHJlZS4mcXVvdDsgb3IgdGhlIGxpbmUgJnF1b3Q7Q2FzZSBrIGlzIG5vdCBhIHRyZWUuJnF1b3Q7LCB3aGVyZSBrIGNvcnJlc3BvbmRzIHRvIHRoZSB0ZXN0IGNhc2UgbnVtYmVyICh0aGV5IGFyZSBzZXF1ZW50aWFsbHkgbnVtYmVyZWQgc3RhcnRpbmcgd2l0aCAxKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=