{"raw_statement":[{"iden":"statement","content":"It is an interesting problem in graph theory called “graph coloring”.\n\n_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)\n\nThe smallest number of colors needed to color a graph is called its chromatic number.\n\n#cf_span(class=[tex-font-style-sc], body=[the student asks]): I wonder if this problem is easy on trees.\n\n#cf_span(class=[tex-font-style-sc], body=[the teacher explains]): Well, two colors is enough for trees.\n\nBut the critical thinking student thought he should better check that. He thought it is too simple to be true. \n\nNote: the tree is a connected graph with no cycles.\n\nThe 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 ≤ 105). The following n - 1 lines contains numbers _a_ and _b_ (1 ≤ a < b ≤ n), meaning that vertices _a_ and _b_ are connected.\n\nFor 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.\n\n"},{"iden":"input","content":"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 ≤ 105). The following n - 1 lines contains numbers _a_ and _b_ (1 ≤ a < b ≤ n), meaning that vertices _a_ and _b_ are connected."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input121 2OutputCase #1: 2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ G_k = (V_k, E_k) $ be a tree with $ n_k $ vertices, where $ V_k = \\{1, 2, \\dots, n_k\\} $.  \n- $ E_k \\subseteq \\binom{V_k}{2} $ is the edge set, given as pairs $ (a, b) $ with $ 1 \\leq a < b \\leq n_k $.  \n\n**Constraints**  \n1. $ 0 \\leq T \\leq 20 $  \n2. For each test case $ k $:  \n   - $ 1 \\leq n_k \\leq 10^5 $  \n   - $ |E_k| = n_k - 1 $  \n   - $ G_k $ is connected and acyclic (i.e., a tree).  \n\n**Objective**  \nFor each test case $ k $, compute the chromatic number $ \\chi(G_k) $ of the tree $ G_k $.","simple_statement":"For any tree, the minimum number of colors needed so that no two connected vertices have the same color is always 2.","has_page_source":false}