codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.