982C.md (1446B)
1 Source: https://codeforces.com/problemset/problem/982/C 2 3 C. Cut 'em all! 4 5 time limit per test 6 7 1 second 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 You're given a tree with $n$ vertices. 22 23 Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size. 24 25 Input 26 27 The first line contains an integer $n$ ($1 \le n \le 10^5$) denoting the size of the tree. 28 29 The next $n - 1$ lines contain two integers $u$, $v$ ($1 \le u, v \le n$) each, describing the vertices connected by the $i$-th edge. 30 31 It's guaranteed that the given edges form a tree. 32 33 Output 34 35 Output a single integer $k$ — the maximum number of edges that can be removed to leave all connected components with even size, or $-1$ if it is impossible to remove edges in order to satisfy this property. 36 37 Examples 38 39 Input 40 41 ``` 42 4 43 2 4 44 4 1 45 3 1 46 ``` 47 48 Output 49 50 ``` 51 1 52 ``` 53 54 Input 55 56 ``` 57 3 58 1 2 59 1 3 60 ``` 61 62 Output 63 64 ``` 65 -1 66 ``` 67 68 Input 69 70 ``` 71 10 72 7 1 73 8 4 74 8 10 75 4 7 76 6 5 77 9 3 78 3 5 79 2 10 80 2 5 81 ``` 82 83 Output 84 85 ``` 86 4 87 ``` 88 89 Input 90 91 ``` 92 2 93 1 2 94 ``` 95 96 Output 97 98 ``` 99 0 100 ``` 101 102 Note 103 104 In the first example you can remove the edge between vertices $1$ and $4$. The graph after that will have two connected components with two vertices in each. 105 106 In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $-1$.