시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 145 22 16 25.397%

문제

간선에 방향성이 있는 트리(사이클이 없는 연결 그래프)가 주어진다. 트리에 특별 경로를 가능한 적게 추가해서, 모든 노드에서 다른 노드로 이동할 수 있게 하는 프로그램을 작성하시오.

특별 경로는 아래와 같은 규칙을 지켜야 한다.

  1. 특별 경로는 연속된 간선과 정점으로 이루어져 있어야 한다.
  2. 특별 경로의 모든 간선은 원래 트리에 있던 간선과 반대 방향이어야 한다.
  3. 특별 경로에서 모든 노드와 간선은 최대 1번 방문할 수 있다.
  4. 두 개 이상의 특별 경로가 같은 노드나 간선을 공유할 수 있다.

아래 트리를 살펴보자. 검정 간선은 원래 트리의 간선을 나타내고, 동그라미는 노드를 나타낸다. 그 다음, 두 개의 특별 경로 2-1-0(초록색)과 3-1(파란색)를 추가한다. 3-1대신에 3-1-0을 추가해도 된다. 하지만, 1-3이나 0-1-2는 규칙 2 때문에 추가할 수 없고, 0-2와 2-3-0은 규칙 1 때문에 추가할 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T(≤30)이 주어진다.

각 테스트 케이스의 첫째 줄에는 노드의 수 N이 주어진다. (2 ≤ N ≤ 20000) 노드는 0번부터 N-1번까지 번호가 매겨져 있다. 다음 N-1줄에는 간선 정보를 나타내는 u와 v가 주어진다. (0 ≤ u, v < N, u ≠ v) u에서 v로 향하는 간선이라는 뜻이다.

출력

각 테스트 케이스에 대해서, 케이스 번호와 모든 노드가 서로 연결될 수 있게 하기 위해서 추가해야 하는 특별 경로 개수의 최솟값을 출력한다.

예제 입력 1

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

예제 출력 1

Case 1: 2
Case 2: 3
W3sicHJvYmxlbV9pZCI6IjU2NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWMgXHVhY2JkXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMDRcdWMxMjBcdWM1ZDAgXHViYzI5XHVkNWE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWQyYjhcdWI5YWMoXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjXHViOTdjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MDFcdWFjOGMgXHVjZDk0XHVhYzAwXHVkNTc0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHViMTc4XHViNGRjXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjOGMgXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1ZDJiOVx1YmNjNCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjXHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFjMDRcdWMxMjBcdWFjZmMgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjNmQwXHViNzk4IFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIzNTggXHVhYzA0XHVjMTIwXHVhY2ZjIFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTVcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWM2NDAgXHVhYzA0XHVjMTIwXHVjNzQwIFx1Y2Q1Y1x1YjMwMCAxXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWIxNzhcdWI0ZGNcdWIwOTggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLiBcdWFjODBcdWM4MTUgXHVhYzA0XHVjMTIwXHVjNzQwIFx1YzZkMFx1Yjc5OCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHViM2Q5XHVhZGY4XHViNzdjXHViYmY4XHViMjk0IFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVkMmI5XHViY2M0IFx1YWNiZFx1Yjg1YyAyLTEtMChcdWNkMDhcdWI4NWRcdWMwYzkpXHVhY2ZjIDMtMShcdWQzMGNcdWI3ODBcdWMwYzkpXHViOTdjIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC4gMy0xXHViMzAwXHVjMmUwXHVjNWQwIDMtMS0wXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgMS0zXHVjNzc0XHViMDk4IDAtMS0yXHViMjk0IFx1YWRkY1x1Y2U1OSAyIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgMC0yXHVjNjQwIDItMy0wXHVjNzQwIFx1YWRkY1x1Y2U1OSAxIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zcGVjaWFscGF0aC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMThweDsgd2lkdGg6MTEwcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgmbGU7MzApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDAwMCkgXHViMTc4XHViNGRjXHViMjk0IDBcdWJjODhcdWJkODBcdWQxMzAgTi0xXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgTi0xXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwNFx1YzEyMCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHVcdWM2NDAgdlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgdSwgdiAmbHQ7IE4sIHUgJm5lOyB2KSB1XHVjNWQwXHVjMTFjIHZcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQyMCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjZDk0XHVhYzAwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQyYjlcdWJjYzQgXHVhY2JkXHViODVjIFx1YWMxY1x1YzIxOFx1Yzc1OCZuYnNwO1x1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTY0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhdGhzIGluIGEgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHRyZWUgKGEgY29ubmVjdGVkIGdyYXBoIHdpdGggbm8gY3ljbGVzKSwgYW5kIHRoZSBlZGdlcyBvZiB0aGUgdHJlZSB3aGljaCBhcmUgZm9yIHNvbWUgcmVhc29uIGRpcmVjdGVkOyB5b3VyIHRhc2sgaXMgdG8gYWRkIG1pbmltdW0gbnVtYmVyIG9mIHNwZWNpYWwgcGF0aHMgaW4gdGhlIHRyZWUgc3VjaCB0aGF0IGl0JiMzOTtzIHBvc3NpYmxlIHRvIGdvIGZyb20gYW55IG5vZGUgdG8gYW5vdGhlci4gVGhlIHJ1bGVzIGZvciB0aGUgc3BlY2lhbCBwYXRocyBhcmUgbm90ZWQgYmVsb3c6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgc3BlY2lhbCBwYXRoIGNvbnNpc3RzIG9mIHNvbWUgY29udGludW91cyBlZGdlcyAoZnJvbSB0aGUgdHJlZSkgYW5kIG5vZGVzLiZuYnNwOzxiciBcLz5cclxuSW4gYSBzcGVjaWFsIHBhdGgsIHRoZSBlZGdlcyBzaG91bGQgYmUgaW4gb3Bwb3NpdGUgZGlyZWN0aW9ucyBhcyB0aGV5IGFyZSBpbiB0aGUgdHJlZS4mbmJzcDs8YnIgXC8+XHJcbkEgbm9kZSBvciBhbiBlZGdlIGNhbiBiZSB2aXNpdGVkIGF0IG1vc3Qgb25jZSBpbiBhIHNwZWNpYWwgcGF0aC4mbmJzcDs8YnIgXC8+XHJcbk11bHRpcGxlIHNwZWNpYWwgcGF0aHMgbWF5IGhhdmUgY29tbW9uIG5vZGVzIG9yIGVkZ2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaW4gdGhlIHBpY3R1cmUgYmVsb3csIGEgdHJlZSBpcyBkcmF3biwgdGhlIGJsYWNrIGFycm93cyByZXByZXNlbnQgdGhlIGVkZ2VzIGFuZCB0aGVpciBkaXJlY3Rpb25zLCBjaXJjbGVzIHJlcHJlc2VudCBub2Rlcy4gVGhlbiB3ZSBuZWVkIHR3byBzcGVjaWFsIHBhdGhzLiBPbmUgcGF0aCBpcyAyLTEtMCAoZ3JlZW4gYXJyb3cpLCBhbm90aGVyIGlzIDMtMSAoYmx1ZSBhcnJvdykuIEluc3RlYWQgb2YgdGhlIHBhdGggMy0xIHdlIGNhbiBhZGQgMy0xLTAuIFlvdSBjYW5ub3QgYWRkIGEgcGF0aCBsaWtlIDEtMyBvciAwLTEtMiBiZWNhdXNlIG9mIHJ1bGUgMi4gWW91IGNhbm5vdCBhZGQgMC0yIG9yIDItMy0wIGJlY2F1c2Ugb2YgcnVsZSAxLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NwZWNpYWxwYXRoLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExOHB4OyB3aWR0aDoxMTBweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgc3RhcnRzIHdpdGggYW4gaW50ZWdlciBUICgmbGU7IDMwKSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5FYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDIwMDAwKSwgd2hlcmUgTiBkZW5vdGVzIHRoZSBudW1iZXIgb2Ygbm9kZXMuIFRoZSBub2RlcyBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIE4tMS4gRWFjaCBvZiB0aGUgbmV4dCBOLTEgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIHUgdiAoMCAmbGU7IHUsIHYgJmx0OyBOLCB1ICZuZTsgdikgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGFuIGVkZ2UgZnJvbSB1IHRvIHYuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgcHJpbnQgdGhlIGNhc2UgbnVtYmVyIGFuZCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3BlY2lhbCBwYXRocyByZXF1aXJlZCBzdWNoIHRoYXQgaXQmIzM5O3MgcG9zc2libGUgdG8gZ28gZnJvbSBhbnkgbm9kZSB0byBhbm90aGVyLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==