시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 502 185 137 34.949%

문제

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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+XHJcblxyXG48cD5cdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuICZsZTsgNTAwXHVhY2ZjIG0gJmxlOyBuKG4tMSlcLzJcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjNWVjXHViN2VjXHViYzg4IFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtObyB0cmVlcy4mcXVvdDtcdWI5N2MsIFx1ZDU1YyBcdWFjMWNcdWI3N2NcdWJhNzQgJnF1b3Q7VGhlcmUgaXMgb25lIHRyZWUuJnF1b3Q7XHViOTdjLCBUXHVhYzFjKFQgJmd0OyAxKVx1Yjc3Y1x1YmE3NCZuYnNwOyZxdW90O0EgZm9yZXN0IG9mIFQgdHJlZXMuJnF1b3Q7XHViOTdjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDgwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyZWVzIiwiZGVzY3JpcHRpb24iOiI8cD5BIGdyYXBoIGNvbnNpc3RzIG9mIGEgc2V0IG9mIHZlcnRpY2VzIGFuZCBlZGdlcyBiZXR3ZWVuIHBhaXJzIG9mIHZlcnRpY2VzLiBUd28gdmVydGljZXMgYXJlIGNvbm5lY3RlZCBpZiB0aGVyZSBpcyBhIHBhdGggKHN1YnNldCBvZiBlZGdlcykgbGVhZGluZyBmcm9tIG9uZSB2ZXJ0ZXggdG8gYW5vdGhlciwgYW5kIGEgY29ubmVjdGVkIGNvbXBvbmVudCBpcyBhIG1heGltYWwgc3Vic2V0IG9mIHZlcnRpY2VzIHRoYXQgYXJlIGFsbCBjb25uZWN0ZWQgdG8gZWFjaCBvdGhlci4gQSBncmFwaCBjb25zaXN0cyBvZiBvbmUgb3IgbW9yZSBjb25uZWN0ZWQgY29tcG9uZW50cy48XC9wPlxyXG5cclxuPHA+QSB0cmVlIGlzIGEgY29ubmVjdGVkIGNvbXBvbmVudCB3aXRob3V0IGN5Y2xlcywgYnV0IGl0IGNhbiBhbHNvIGJlIGNoYXJhY3Rlcml6ZWQgaW4gb3RoZXIgd2F5cy4gRm9yIGV4YW1wbGUsIGEgdHJlZSBjb25zaXN0aW5nIG9mIG4gdmVydGljZXMgaGFzIGV4YWN0bHkgbi0xIGVkZ2VzLiBBbHNvLCB0aGVyZSBpcyBhIHVuaXF1ZSBwYXRoIGNvbm5lY3RpbmcgYW55IHBhaXIgb2YgdmVydGljZXMgaW4gYSB0cmVlLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGdyYXBoLCByZXBvcnQgdGhlIG51bWJlciBvZiBjb25uZWN0ZWQgY29tcG9uZW50cyB0aGF0IGFyZSBhbHNvIHRyZWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGNhc2VzLiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBuIGFuZCBtLCBzYXRpc2Z5aW5nIG4gJmxlOyA1MDAgYW5kIG0gJmxlOyBuKG4tMSlcLzIuIFRoaXMgaXMgZm9sbG93ZWQgYnkgbSBsaW5lcywgZWFjaCBjb250YWluaW5nIHR3byBpbnRlZ2VycyBzcGVjaWZ5aW5nIHRoZSB0d28gZGlzdGluY3QgdmVydGljZXMgY29ubmVjdGVkIGJ5IGFuIGVkZ2UuIE5vIGVkZ2Ugd2lsbCBiZSBzcGVjaVx1ZmIwMWVkIHR3aWNlIChvciBnaXZlbiBhZ2FpbiBpbiBhIGRpZmZlcmVudCBvcmRlcikuIFRoZSB2ZXJ0aWNlcyBhcmUgbGFiZWxsZWQgMSB0byBuLiBUaGUgZW5kIG9mIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBuID0gbSA9IDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgcHJpbnQgb25lIG9mIHRoZSBmb2xsb3dpbmcgbGluZXMgZGVwZW5kaW5nIG9uIGhvdyBtYW55IGRpZmZlcmVudCBjb25uZWN0ZWQgY29tcG9uZW50cyBhcmUgdHJlZXMgKFQgJmd0OyAxIGJlbG93KTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5DYXNlIHg6IEEgZm9yZXN0IG9mIFQgdHJlZXMuPFwvbGk+XHJcblx0PGxpPkNhc2UgeDogVGhlcmUgaXMgb25lIHRyZWUuPFwvbGk+XHJcblx0PGxpPkNhc2UgeDogTm8gdHJlZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+eCBpcyB0aGUgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGZyb20gMSkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: jh05013