#P18120. Leaf Meeting
Leaf Meeting
Leaf Meeting
给定一棵 个顶点的无向树。度数为1的顶点称为叶子;每个叶子最初放有一个棋子。
对每个从叶子 出发的棋子,独立选择一个无限的叶子序列 ,要求 且 。棋子先沿最短路径从 走向 ,再从 走向 ,如此无限继续。
每一步,所有棋子同时沿各自路线走过恰好一条边,不能停留。判断能否选择这些路线,使所有棋子在某个有限时刻同时位于同一个叶子。
输入格式
第一行整数 ,。
每组第一行整数 ,。接下来 行,每行两个顶点 ,,保证构成一棵树。
所有数据的 之和不超过200000。
输出格式
每组输出 YES 或 NO,表示是否存在符合要求的路线。
样例
5
2
1 2
3
2 1
2 3
4
1 2
1 3
3 4
6
1 2
2 3
2 4
4 5
4 6
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
NO
NO
NO
NO
YES