{"problem":{"name":"L. Starry Night","description":{"content":"Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading ou","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10110L"},"statements":[{"statement_type":"Markdown","content":"Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading out of it. A ray is a chain of connected nodes where each node except for the last one is connected to exactly two nodes, and the last one is connected to exactly one node. \n\nThe first line of input contains a single integer T, the number of test cases.\n\nThe first line of each test case contains a single integers N (1 ≤ N ≤ 105), the number of nodes in the sky.\n\nEach of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes.\n\nIt is guaranteed that the given graph is a tree.\n\nFor each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line.\n\nA tree is an undirected graph with exactly one path between any two nodes.\n\n## Input\n\nThe first line of input contains a single integer T, the number of test cases.The first line of each test case contains a single integers N (1 ≤ N ≤ 105), the number of nodes in the sky.Each of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes.It is guaranteed that the given graph is a tree.\n\n## Output\n\nFor each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line.\n\n[samples]\n\n## Note\n\nA tree is an undirected graph with exactly one path between any two nodes.","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, let $ G = (V, E) $ be a tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges.  \n\nA **star** is a node $ v \\in V $ of degree $ \\deg(v) \\geq 3 $, such that each of its incident edges leads to a **ray**: a path (possibly of length 1) where all internal nodes (if any) have degree 2, and the terminal node has degree 1.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. For each test case: $ 1 \\leq N \\leq 10^5 $  \n3. The graph is a tree.  \n\n**Objective**  \nFind the maximum number of stars that can be formed by removing zero or more nodes from the tree, such that each star is a node of degree $ \\geq 3 $, and each of its incident edges extends into a valid ray (as defined).  \n\n**Note**: Removal of a node also removes all incident edges. The goal is to maximize the count of such star nodes under the ray constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10110L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}