How Many Subtrees?

Trees are used for all sorts of purposes, such as parsing, information storage and retrieval, and sorting. An unweighted, undirected, unrooted tree T is made up of vertices and edges. Each edge connects two vertices. In a tree, any pair of vertices must be connected by some path of edges and vertices through the tree, but only one simple path can connect them (cycles are not permitted). A tree with V vertices must have V-1 edges.

Computer science uses a lot of trees, but there are even more than might appear at first glance, because every tree is itself made up of one or more subtrees. A subtree S of a tree T is itself a tree, made only from the vertices and edges of T. A subtree must have at least one vertex, and a tree is considered a subtree of itself. Here is an example of a tree with four vertices (the large tree on the left) and its 11 subtrees (the smaller trees in the box on the right):

Write a program that, for each given tree, determines the number of subtrees it has.

The input file contains multiple test cases, each describing a tree. Each test case starts with an integer 1 ≤ V ≤ 10 giving the number of vertices in the tree. Vertices are implicitly labeled 0 through V-1. V is followed by V-1 edge descriptions. Each edge description has two integers 0 ≤ A < V and 0 ≤ B < V, where A ≠ B, indicating that the endpoints A and B are connected. The last test case is followed by a line containing a single zero.

For each test case, print the case number (beginning with 1) followed by the number of subtrees. Follow the format of the sample output.