401481: GYM100482 A Colorful Tree

It is an interesting problem in graph theory called “graph coloring”.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. (from Wikipedia)

The smallest number of colors needed to color a graph is called its chromatic number.

the student asks: I wonder if this problem is easy on trees.

the teacher explains: Well, two colors is enough for trees.

But the critical thinking student thought he should better check that. He thought it is too simple to be true.

Note: the tree is a connected graph with no cycles.

The first line contains the number of test cases T (0 ≤ T ≤ 20). The first line of each test case contains the number of vertices in the tree, n (1 ≤ n ≤ 10⁵). The following n - 1 lines contains numbers a and b (1 ≤ a < b ≤ n), meaning that vertices a and b are connected.

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the chromatic number of the given tree.

1
2
1 2

Case #1: 2