← 返回题目
题库练习 【树形动态规划】Ksyusha and Chinchilla
← 上一题 下一题 →

A4779 | 【树形动态规划】Ksyusha and Chinchilla

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

Ksyusha有一只宠物龙猫、一棵有 $n$ 个顶点的树和巨大的剪刀。一棵树是一个没有循环的连接图。在一节枯燥的物理课上，Ksyusha想到了如何逗她的宠物开心。

宠物龙猫喜欢玩树枝。一个树枝是一棵有3个顶点的树。


![](/uploads/acgo/image/cbc897304594c7f0_2efc0768f17c.png)


该树枝看起来像这样。

切割是指去除树上的一些（尚未切割的）边缘。Ksyusha有大量的空闲时间，所以她能负担得起足够多的切割，从而使树分裂成分支。换句话说，经过几次（可能是零）切割后，每个顶点必须正好属于一个分支。

帮助Ksyusha选择要切割的边，或者告诉他这是不可能的。

输入格式

第一行包含一个整数 $n$ (2≤n≤2*$10^5$)，表示树中顶点的数量。

接下来的 $n-1$行，表示 $n-1$ 条边。

每一行有两个整数 $u_i$ 和 $v_i$ ，表示第 $i$ 条边。 (1≤$u_i,$ $v_i$≤n)

可以保证这组边形成一棵树。

输出格式

如果所需的切树方式不存在，输出 $-1$。

否则，输出一个整数 $k$，表示要切割的边的数量。

输入输出样例

输入 #1
9
1 2
4 3
7 9
5 4
4 6
3 2
8 7
1 7
输出 #1
2
输入 #2
5
1 3
5 3
5 2
3 4
输出 #2
-1
C++ 编辑器
输入
输出