시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB174085963416732.275%

문제

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

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

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

입력

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

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "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.
W3sicHJvYmxlbV9pZCI6IjQ4MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM4MTVcdWM4MTBcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzVmMFx1YWNiMCBcdWM2OTRcdWMxOGNcdWIyOTQgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzVmMFx1YWNiMCBcdWM2OTRcdWMxOGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVjNWYwXHVhY2IwIFx1YzY5NFx1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVkMmI4XHViOWFjXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWMxMzFcdWM5YzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQyYjhcdWI5YWNcdWIyOTQgXHVjODE1XHVjODEwXHVjNzc0IG5cdWFjMWMsIFx1YWMwNFx1YzEyMFx1Yzc3NCBuLTFcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWI0NTAgXHVjODE1XHVjODEwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuICZsZTsgNTAwXHVhY2ZjIG0gJmxlOyBuKG4tMSlcLzJcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBuXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQgJnF1b3Q7Tm8gdHJlZXMuJnF1b3Q7XHViOTdjLCBcdWQ1NWMgXHVhYzFjXHViNzdjXHViYTc0ICZxdW90O1RoZXJlIGlzIG9uZSB0cmVlLiZxdW90O1x1Yjk3YywgVFx1YWMxYyhUICZndDsgMSlcdWI3N2NcdWJhNzQmbmJzcDsmcXVvdDtBIGZvcmVzdCBvZiBUIHRyZWVzLiZxdW90O1x1Yjk3YyBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ4MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBncmFwaCBjb25zaXN0cyBvZiBhIHNldCBvZiB2ZXJ0aWNlcyBhbmQgZWRnZXMgYmV0d2VlbiBwYWlycyBvZiB2ZXJ0aWNlcy4gVHdvIHZlcnRpY2VzIGFyZSBjb25uZWN0ZWQgaWYgdGhlcmUgaXMgYSBwYXRoIChzdWJzZXQgb2YgZWRnZXMpIGxlYWRpbmcgZnJvbSBvbmUgdmVydGV4IHRvIGFub3RoZXIsIGFuZCBhIGNvbm5lY3RlZCBjb21wb25lbnQgaXMgYSBtYXhpbWFsIHN1YnNldCBvZiB2ZXJ0aWNlcyB0aGF0IGFyZSBhbGwgY29ubmVjdGVkIHRvIGVhY2ggb3RoZXIuIEEgZ3JhcGggY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgY29ubmVjdGVkIGNvbXBvbmVudHMuPFwvcD5cclxuXHJcbjxwPkEgdHJlZSBpcyBhIGNvbm5lY3RlZCBjb21wb25lbnQgd2l0aG91dCBjeWNsZXMsIGJ1dCBpdCBjYW4gYWxzbyBiZSBjaGFyYWN0ZXJpemVkIGluIG90aGVyIHdheXMuIEZvciBleGFtcGxlLCBhIHRyZWUgY29uc2lzdGluZyBvZiBuIHZlcnRpY2VzIGhhcyBleGFjdGx5IG4tMSBlZGdlcy4gQWxzbywgdGhlcmUgaXMgYSB1bmlxdWUgcGF0aCBjb25uZWN0aW5nIGFueSBwYWlyIG9mIHZlcnRpY2VzIGluIGEgdHJlZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBncmFwaCwgcmVwb3J0IHRoZSBudW1iZXIgb2YgY29ubmVjdGVkIGNvbXBvbmVudHMgdGhhdCBhcmUgYWxzbyB0cmVlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBjYXNlcy4gRWFjaCBjYXNlIHN0YXJ0cyB3aXRoIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgbiBhbmQgbSwgc2F0aXNmeWluZyBuICZsZTsgNTAwIGFuZCBtICZsZTsgbihuLTEpXC8yLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG0gbGluZXMsIGVhY2ggY29udGFpbmluZyB0d28gaW50ZWdlcnMgc3BlY2lmeWluZyB0aGUgdHdvIGRpc3RpbmN0IHZlcnRpY2VzIGNvbm5lY3RlZCBieSBhbiBlZGdlLiBObyBlZGdlIHdpbGwgYmUgc3BlY2lcdWZiMDFlZCB0d2ljZSAob3IgZ2l2ZW4gYWdhaW4gaW4gYSBkaWZmZXJlbnQgb3JkZXIpLiBUaGUgdmVydGljZXMgYXJlIGxhYmVsbGVkIDEgdG8gbi4gVGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgbiA9IG0gPSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIHByaW50IG9uZSBvZiB0aGUgZm9sbG93aW5nIGxpbmVzIGRlcGVuZGluZyBvbiBob3cgbWFueSBkaWZmZXJlbnQgY29ubmVjdGVkIGNvbXBvbmVudHMgYXJlIHRyZWVzIChUICZndDsgMSBiZWxvdyk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q2FzZSB4OiBBIGZvcmVzdCBvZiBUIHRyZWVzLjxcL2xpPlxyXG5cdDxsaT5DYXNlIHg6IFRoZXJlIGlzIG9uZSB0cmVlLjxcL2xpPlxyXG5cdDxsaT5DYXNlIHg6IE5vIHRyZWVzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPnggaXMgdGhlIGNhc2UgbnVtYmVyIChzdGFydGluZyBmcm9tIDEpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Rocky Mountain Regional > 2012 Rocky Mountain Regional Contest H번