{"problem":{"name":"A. Colorful Tree","description":{"content":"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”","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10048A"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10048A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}