Кто-то незнакомый подарил Ване на день рождения ежа — связный неориентированный граф, состоящий из одной вершины степени хотя бы $$$3$$$, которую мы будем называть центром, и нескольких вершин степени 1. Ваня посчитал, что ёж — это слишком скучный граф, и решил сделать $$$k$$$-мультиёж.
Определим $$$k$$$-мультиёж следующим образом:
Таким образом, $$$k$$$-мультиёж является деревом. Ваня сделал $$$k$$$-мультиёж, но не уверен, что нигде не ошибся, поэтому попросил вас проверить, является ли созданное им дерево $$$k$$$-мультиежом.
В первой строке записано $$$2$$$ числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 10^{9}$$$) — количество вершин дерева и параметр ежа.
В следующих $$$n-1$$$ строках описаны рёбра дерева. Каждое ребро описывается парой $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) вершин, которые оно соединяет.
Гарантируется, что описанный граф является деревом.
Выведите "Yes" (без кавычек), если граф является $$$k$$$-мультиежом, и "No" (без кавычек), если не является.
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
3 1
1 3
2 3
No
2-мультиёж из первого примера выглядит так:
Его центр — вершина $$$13$$$. Ежи, созданные на последнем шаге: [4 (центр), 1, 2, 3], [6 (центр), 7, 8, 9], [5 (центр), 10, 11, 12, 13].
Дерево из второго примера не является ежом, потому что степень центра должна быть хотя бы $$$3$$$.
Название |
---|