I found an interesting problem on https://codeforces.com/problemset/problem/1375/G:
You are given a tree with $n$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:  Choose three vertices $a$, $b$, and $c$ such that $b$ is adjacent to both $a$ and $c$.  For every vertex $d$ other than $b$ that is adjacent to $a$, remove the edge connecting $d$ and $a$ and add the edge connecting $d$ and $c$.  Delete the edge connecting $a$ and $b$ and add the edge connecting $a$ and $c$. 

As an example, consider the following tree: [Image] 

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $2$, $4$, and $5$: [Image] 

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $n - 1$, called its center, and $n - 1$ vertices of degree $1$.


-----Input-----

The first line contains an integer $n$ ($3 \le n \le 2 \cdot 10^5$)  — the number of vertices in the tree.

The $i$-th of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) denoting that there exists an edge connecting vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.


-----Output-----

Print a single integer  — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $10^{18}$ operations.


-----Examples-----
Input
6
4 5
2 6
3 2
1 2
2 4

Output
1

Input
4
2 4
4 1
3 4

Output
0



-----Note-----

The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $5$ by applying a single operation to vertices $2$, $4$, and $5$.

In the second test case, the given tree is already a star with the center at vertex $4$, so no operations have to be performed.

I tried it in Python, but could not do it. Can you solve it?
from collections import defaultdict
n = int(input())
graph = defaultdict(list)
for i in range(n - 1):
    l = list(map(int, input().split()))
    graph[l[0]].append(l[1])
    graph[l[1]].append(l[0])
color_v = [-1]*(n + 1)
color_v[1] = 0
q = [1]
while q:
    x = q.pop()
    for i in graph[x]:
        if color_v[i] == -1:
            color_v[i] = 1 - color_v[x]
            q.append(i)
print(min(color_v.count(1), color_v.count(0)) - 1)