Кто-то незнакомый подарил Ване на день рождения ежа — связный неориентированный граф, состоящий из одной вершины степени хотя бы \(3\), которую мы будем называть центром, и нескольких вершин степени 1. Ваня посчитал, что ёж — это слишком скучный граф, и решил сделать \(k\)-мультиёж.
Определим \(k\)-мультиёж следующим образом:
- \(1\)-мультиёж — это ёж: одна вершина степени хотя бы \(3\) и несколько вершин степени 1.
- Для всех \(k \ge 2\), \(k\)-мультиёж — это \((k-1)\)-мультиёж, для каждой висячей вершины \(v\) которого проделали следующие операции: пусть \(u\) — её единственный сосед, удалим вершину \(v\), создадим новый ёж с центром в вершине \(w\), соединим ребром вершины \(u\) и \(w\). Новые ежи могут отличаться как друг от друга, так и от подаренного Ване.
Таким образом, \(k\)-мультиёж является деревом. Ваня сделал \(k\)-мультиёж, но не уверен, что нигде не ошибся, поэтому попросил вас проверить, является ли созданное им дерево \(k\)-мультиежом.
Выходные данные
Выведите "Yes" (без кавычек), если граф является \(k\)-мультиежом, и "No" (без кавычек), если не является.
Примечание
2-мультиёж из первого примера выглядит так:
Его центр — вершина \(13\). Ежи, созданные на последнем шаге: [4 (центр), 1, 2, 3], [6 (центр), 7, 8, 9], [5 (центр), 10, 11, 12, 13].
Дерево из второго примера не является ежом, потому что степень центра должна быть хотя бы \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
14 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
|
Yes
|
|
2
|
3 1
1 3
2 3
|
No
|