1830A.md (2077B)
1 Source: https://codeforces.com/problemset/problem/1830/A 2 3 A. Copil Copac Draws Trees 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Copil Copac is given a list of $n-1$ edges describing a tree of $n$ vertices. He decides to draw it using the following algorithm: 22 23 * Step $0$: Draws the first vertex (vertex $1$). Go to step $1$. 24 * Step $1$: For every edge in the input, in order: if the edge connects an already drawn vertex $u$ to an undrawn vertex $v$, he will draw the undrawn vertex $v$ and the edge. After checking every edge, go to step $2$. 25 * Step $2$: If all the vertices are drawn, terminate the algorithm. Else, go to step $1$. 26 27 The number of readings is defined as the number of times Copil Copac performs step $1$. 28 29 Find the number of readings needed by Copil Copac to draw the tree. 30 31 Input 32 33 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices of the tree. 36 37 The following $n - 1$ lines of each test case contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) — indicating that $(u_i,v_i)$ is the $i$-th edge in the list. It is guaranteed that the given edges form a tree. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output the number of readings Copil Copac needs to draw the tree. 44 45 Example 46 47 Input 48 49 ``` 50 2 51 52 6 53 54 4 5 55 56 1 3 57 58 1 2 59 60 3 4 61 62 1 6 63 64 7 65 66 5 6 67 68 2 4 69 70 2 7 71 72 1 3 73 74 1 2 75 76 4 5 77 ``` 78 79 Output 80 81 ``` 82 2 83 3 84 ``` 85 86 Note 87 88 In the first test case: 89 90 After the first reading, the tree will look like this: 91 92  93 94 After the second reading: 95 96  97 98 Therefore, Copil Copac needs $2$ readings to draw the tree.