森林深处有一棵古树,里面有 $$$n$$$ 蚂蚁,住在 $$$n$$$ 个小房子里,索引从 $$$1$$$ 到 $$$n$$$,由树枝连接。
每年一次,所有的蚂蚁都需要聚集在一起观看 EUC。为此,所有蚂蚁都会沿着它们所居住的树的 $$$n-1$$$ 树枝移动,并在一只蚂蚁的家中相遇。
然而,今年蚂蚁们无法就集合地点达成一致,需要你的帮助来集合。如果有一根分支直接连接 $$$u$$$ 房子里的所有蚂蚁,你可以告诉 $$$u$$$ 房子里的所有蚂蚁搬到 $$$v$$$ 房子。然而,如果 $$$v$$$ 房子里聚集的蚂蚁比 $$$u$$$ 房子里聚集的蚂蚁少,也就是说,如果 $$$v$$$ 房子里的蚂蚁更容易移动,蚂蚁就会忽略你的命令。如果当前房子里根本没有蚂蚁$$$v$$$,这甚至也成立。您可以根据需要多次发出此类命令。
你有可能将所有蚂蚁聚集在一个房子里吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 200\,000$$$) — 蚂蚁家园的数量。
以下 $$$n-1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v\leq n$$$) — 有一个分支直接连接房屋 $$$u$$$ 和房屋 $$$v$$$。保证每只蚂蚁只要沿着树枝就可以到达任何其他蚂蚁的房子。
输出
如果可以将所有蚂蚁聚集在一个房子里,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。
示例
输入 #1
7 5 1 3 2 4 6 3 6 7 1 1 3
输出 #1
YES
输入 #2
5 1 4 4 2 3 2 5 3
输出 #2
NO
输入 #3
6 4 5 5 6 6 1 2 6 3 2
输出 #3
YES
注意
在第一个示例中,您可以收集 $$$3$$$ 房子里的所有蚂蚁,如下所示:
- 你告诉 $$$4$$$ 房子里的蚂蚁搬到 $$$6$$$ 房子。
- 你告诉 $$$2$$$ 房子里的蚂蚁搬到 $$$3$$$ 房子。
- 你告诉 $$$6$$$ 房子里的两只蚂蚁搬到 $$$3$$$ 房子(里面已经有两只蚂蚁)。
- 你告诉 $$$5$$$ 房子里的蚂蚁搬到 $$$1$$$ 房子。
- 你告诉 $$$7$$$ 房子里的蚂蚁搬到 $$$1$$$ 房子(里面已经有两只蚂蚁)。
- 你告诉 $$$1$$$ 房子里的三只蚂蚁搬到 $$$3$$$ 房子(里面已经有四只蚂蚁)。
在第二个样本中,不可能将所有蚂蚁聚集在一个房子里。