서브트리는 몇 개인가?

트리는 파싱, 정보 저장과 검색, 정렬 등 여러 목적으로 쓰인다. 가중치가 없고 방향이 없으며 루트가 없는 트리 T는 정점과 간선으로 이루어진다. 각 간선은 두 정점을 연결한다. 트리에서 임의의 두 정점은 트리 안의 간선과 정점을 지나는 어떤 경로로 반드시 연결되지만, 단순 경로는 오직 하나만 존재할 수 있다(사이클은 허용되지 않는다). 정점이 V개인 트리는 반드시 V-1개의 간선을 가진다.

컴퓨터 과학에는 트리가 많지만, 실제로는 언뜻 보이는 것보다 훨씬 많다. 모든 트리 자체가 하나 이상의 서브트리로 이루어져 있기 때문이다. 트리 T의 서브트리 S는 T의 정점과 간선만으로 이루어진, 그 자체로 트리인 구조다. 서브트리는 정점을 최소 하나 가져야 하며, 트리는 자기 자신을 서브트리로 가진다. 다음은 정점이 네 개인 트리(왼쪽의 큰 트리)와 그 11개의 서브트리(오른쪽 상자 안의 작은 트리들)의 예이다.

주어진 각 트리에 대해 서브트리의 개수를 구하는 프로그램을 작성하시오.

입력 파일은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 트리 하나를 나타낸다. 각 테스트 케이스는 트리의 정점 개수를 나타내는 정수 1 ≤ V ≤ 10으로 시작한다. 정점에는 암묵적으로 0부터 V-1까지의 번호가 붙는다. V 다음에는 V-1개의 간선 설명이 온다. 각 간선 설명은 두 정수 0 ≤ A < V와 0 ≤ B < V로 이루어지며, A ≠ B이고 A와 B가 연결되어 있음을 나타낸다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 케이스 번호(1부터 시작)와 서브트리의 개수를 출력한다. 출력 형식은 예시 출력을 따른다.