Лимак — маленький мишка, который учится рисовать. Люди обычно начинают с домиков, заборов и цветов, ну а мишкам с чего бы так делать? Лимак живет в лесу и решает нарисовать дерево.
Напомним, что деревом называется связный граф, состоящий из n вершин и n - 1 ребра (n ≥ 1).
Лимак выбрал дерево, состоящее из n вершин. У него есть бесконечная полоска бумаги с двумя параллельными рядами точек. Маленький мишка хочет сопоставить вершины дерева некоторым n различным точкам так, чтобы рёбра могли пересекаться только в своих конечных точках — иными словами, должно получиться планарное изображение дерева. Ниже приведен один из корректных рисунков к первому тесту.
Сможет ли Лимак нарисовать выбранное дерево?
В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество вершин в дереве.
В следующих n - 1 строках содержится описание рёбер дерева. i-я из них содержит два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), обозначающих ребро между вершинами ai и bi. Гарантируется, что данное описание задаёт дерево.
Выведите "Yes" (без кавычек), если Лимак может нарисовать выбранное дерево. В противном случае, выведите "No" (без кавычек).
8 1 2 1 3 1 6 6 4 6 7 6 5 7 8
Yes
13 1 2 1 3 1 4 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
No
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач