트리 경로

방향이 있는 트리(사이클이 없는 연결 그래프)가 주어진다. 이 트리에 특별 경로를 최소 개수로 추가하여, 어떤 노드에서 출발하더라도 다른 모든 노드로 이동할 수 있도록(즉, 그래프가 강하게 연결되도록) 만드는 프로그램을 작성하시오.

특별 경로는 다음 규칙을 모두 만족해야 한다.

1. 특별 경로는 트리에서 서로 이어진 간선과 정점으로 이루어진 하나의 경로여야 한다.
2. 특별 경로의 모든 간선은 원래 트리에 있던 간선과 방향이 반대여야 한다.
3. 하나의 특별 경로 안에서 각 노드와 각 간선은 최대 한 번만 지날 수 있다.
4. 서로 다른 특별 경로끼리는 같은 노드나 간선을 공유해도 된다.

예를 들어 노드 0, 1, 2, 3과 간선 0→1, 1→2, 1→3으로 이루어진 트리를 생각하자. 여기에 특별 경로 2→1→0과 3→1을 추가하면 모든 노드가 서로 오갈 수 있게 된다(3→1 대신 3→1→0을 추가해도 된다). 반면 1→3이나 0→1→2는 규칙 2(간선의 방향이 반대여야 함)를 어기므로 추가할 수 없고, 0→2나 2→3→0은 규칙 1(트리에 실제로 존재하는 간선을 따라 이어져야 함)을 어기므로 추가할 수 없다.

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

각 테스트 케이스의 첫째 줄에는 노드의 개수 $N$ ($2 \le N \le 20000$)이 주어진다. 노드는 $0$번부터 $N-1$번까지 번호가 매겨져 있다. 이어지는 $N-1$개의 줄에는 각각 두 정수 $u$와 $v$ ($0 \le u, v < N$, $u \ne v$)가 주어지며, 이는 $u$에서 $v$로 향하는 간선을 뜻한다.

각 테스트 케이스마다 한 줄에 Case k: x 형식으로 출력한다. 여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, $x$는 모든 노드가 서로 오갈 수 있도록 만들기 위해 추가해야 하는 특별 경로 개수의 최솟값이다.