시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 464 172 130 35.616%

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, 두 개 이상이라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

예제 입력 1

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

예제 출력 1

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.
W3sicHJvYmxlbV9pZCI6IjQ4MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM4MTVcdWM4MTBcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzVmMFx1YWNiMCBcdWM2OTRcdWMxOGNcdWIyOTQgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzVmMFx1YWNiMCBcdWM2OTRcdWMxOGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMmI4XHViOWFjXHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVjNWYwXHVhY2IwIFx1YzY5NFx1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVkMmI4XHViOWFjXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWMxMzFcdWM5YzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQyYjhcdWI5YWNcdWIyOTQgXHVjODE1XHVjODEwXHVjNzc0IG5cdWFjMWMsIFx1YWMwNFx1YzEyMFx1Yzc3NCBuLTFcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWI0NTAgXHVjODE1XHVjODEwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuICZsZTsgNTAwXHVhY2ZjIG0gJmxlOyBuKG4tMSlcLzJcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjNWVjXHViN2VjXHViYzg4IFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtObyB0cmVlcy4mcXVvdDtcdWI5N2MsIFx1ZDU1YyBcdWFjMWNcdWI3N2NcdWJhNzQgJnF1b3Q7VGhlcmUgaXMgb25lIHRyZWUuJnF1b3Q7XHViOTdjLCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc3NFx1Yjc3Y1x1YmE3NCAmcXVvdDtBIGZvcmVzdCBvZiBUIHRyZWVzLiZxdW90O1x1Yjk3YyBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBncmFwaCBjb25zaXN0cyBvZiBhIHNldCBvZiB2ZXJ0aWNlcyBhbmQgZWRnZXMgYmV0d2VlbiBwYWlycyBvZiB2ZXJ0aWNlcy4gVHdvIHZlcnRpY2VzIGFyZSBjb25uZWN0ZWQgaWYgdGhlcmUgaXMgYSBwYXRoIChzdWJzZXQgb2YgZWRnZXMpIGxlYWRpbmcgZnJvbSBvbmUgdmVydGV4IHRvIGFub3RoZXIsIGFuZCBhIGNvbm5lY3RlZCBjb21wb25lbnQgaXMgYSBtYXhpbWFsIHN1YnNldCBvZiB2ZXJ0aWNlcyB0aGF0IGFyZSBhbGwgY29ubmVjdGVkIHRvIGVhY2ggb3RoZXIuIEEgZ3JhcGggY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgY29ubmVjdGVkIGNvbXBvbmVudHMuPFwvcD5cclxuXHJcbjxwPkEgdHJlZSBpcyBhIGNvbm5lY3RlZCBjb21wb25lbnQgd2l0aG91dCBjeWNsZXMsIGJ1dCBpdCBjYW4gYWxzbyBiZSBjaGFyYWN0ZXJpemVkIGluIG90aGVyIHdheXMuIEZvciBleGFtcGxlLCBhIHRyZWUgY29uc2lzdGluZyBvZiBuIHZlcnRpY2VzIGhhcyBleGFjdGx5IG4tMSBlZGdlcy4gQWxzbywgdGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBjb25uZWN0aW5nIGFueSBwYWlyIG9mIHZlcnRpY2VzIGluIGEgdHJlZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBncmFwaCwgcmVwb3J0IHRoZSBudW1iZXIgb2YgY29ubmVjdGVkIGNvbXBvbmVudHMgdGhhdCBhcmUgYWxzbyB0cmVlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBjYXNlcy4gRWFjaCBjYXNlIHN0YXJ0cyB3aXRoIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgbiBhbmQgbSwgc2F0aXNmeWluZyBuICZsZTsgNTAwIGFuZCBtICZsZTsgbihuLTEpXC8yLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG0gbGluZXMsIGVhY2ggY29udGFpbmluZyB0d28gaW50ZWdlcnMgc3BlY2lmeWluZyB0aGUgdHdvIGRpc3RpbmN0IHZlcnRpY2VzIGNvbm5lY3RlZCBieSBhbiBlZGdlLiBObyBlZGdlIHdpbGwgYmUgc3BlY2lcdWZiMDFlZCB0d2ljZSAob3IgZ2l2ZW4gYWdhaW4gaW4gYSBkaWZmZXJlbnQgb3JkZXIpLiBUaGUgdmVydGljZXMgYXJlIGxhYmVsbGVkIDEgdG8gbi4gVGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgbiA9IG0gPSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIHByaW50IG9uZSBvZiB0aGUgZm9sbG93aW5nIGxpbmVzIGRlcGVuZGluZyBvbiBob3cgbWFueSBkaWZmZXJlbnQgY29ubmVjdGVkIGNvbXBvbmVudHMgYXJlIHRyZWVzIChUICZndDsgMSBiZWxvdyk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q2FzZSB4OiBBIGZvcmVzdCBvZiBUIHRyZWVzLjxcL2xpPlxyXG5cdDxsaT5DYXNlIHg6IFRoZXJlIGlzIG9uZSB0cmVlLjxcL2xpPlxyXG5cdDxsaT5DYXNlIHg6IE5vIHRyZWVzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPnggaXMgdGhlIGNhc2UgbnVtYmVyIChzdGFydGluZyBmcm9tIDEpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==