{"raw_statement":[{"iden":"statement","content":"You're given a tree with $n$ vertices.\n\nYour 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."},{"iden":"input","content":"The first line contains an integer $n$ ($1 \\le n \\le 10^5$) denoting the size of the tree.\n\nThe 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.\n\nIt's guaranteed that the given edges form a tree."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n4\n2 4\n4 1\n3 1\n\nOutput\n\n1\n\nInput\n\n3\n1 2\n1 3\n\nOutput\n\n\\-1\n\nInput\n\n10\n7 1\n8 4\n8 10\n4 7\n6 5\n9 3\n3 5\n2 10\n2 5\n\nOutput\n\n4\n\nInput\n\n2\n1 2\n\nOutput\n\n0"},{"iden":"note","content":"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.\n\nIn 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$."}],"translated_statement":[{"iden":"statement","content":"你被给定一棵包含 $n$ 个顶点的树。\n\n你的任务是确定最多可以删除多少条边，使得所有剩余的连通分量的大小均为偶数。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)，表示树的大小。\n\n接下来的 $n - 1$ 行每行包含两个整数 $u$, $v$ ($1 lt.eq u, v lt.eq n$)，描述第 $i$ 条边连接的两个顶点。\n\n保证给定的边构成一棵树。\n\n请输出一个整数 $k$ —— 最多可以删除的边数，使得所有连通分量的大小均为偶数；如果不可能通过删除边满足此性质，则输出 $-1$。\n\n在第一个例子中，你可以删除顶点 $1$ 和 $4$ 之间的边。删除后，图将有两个连通分量，每个分量包含两个顶点。\n\n在第二个例子中，你无法删除边使得所有连通分量都具有偶数个顶点，因此答案为 $-1$。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)，表示树的大小。接下来的 $n - 1$ 行每行包含两个整数 $u$, $v$ ($1 lt.eq u, v lt.eq n$)，描述第 $i$ 条边连接的两个顶点。保证给定的边构成一棵树。"},{"iden":"output","content":"请输出一个整数 $k$ —— 最多可以删除的边数，使得所有连通分量的大小均为偶数；如果不可能通过删除边满足此性质，则输出 $-1$。"},{"iden":"examples","content":"输入\n4\n2 4\n4 1\n3 1\n输出\n1\n\n输入\n3\n1 2\n1 3\n输出\n-1\n\n输入\n10\n7 1\n8 4\n8 10\n4 7\n6 5\n9 3\n3 5\n2 10\n2 5\n输出\n4\n\n输入\n2\n1 2\n输出\n0"},{"iden":"note","content":"在第一个例子中，你可以删除顶点 $1$ 和 $4$ 之间的边。删除后，图将有两个连通分量，每个分量包含两个顶点。在第二个例子中，你无法删除边使得所有连通分量都具有偶数个顶点，因此答案为 $-1$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.\n\nFor any subset $ E' \\subseteq E $, let $ G' = (V, E \\setminus E') $ be the resulting forest after removing edges in $ E' $.  \nLet $ C_1, C_2, \\dots, C_k $ be the connected components of $ G' $, and let $ |C_i| $ denote the number of vertices in component $ C_i $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. The graph $ T $ is a tree (connected, acyclic, undirected).  \n\n**Objective**  \nFind the maximum number of edges $ |E'| $ that can be removed such that:  \n$$\n\\forall i, \\; |C_i| \\equiv 0 \\pmod{2}\n$$  \nIf no such $ E' $ exists, output $ -1 $.  \n\n**Note**: Removing an edge splits a component into two; the process is equivalent to partitioning the tree into even-sized connected components.","simple_statement":null,"has_page_source":false}