D. Как килька в банке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тема боя с Элитной Четверкой — Дзюничи Масуда, Pokémon Black & White

Пусть $$$n, k$$$ — положительные целые числа. Вам дано дерево$$$^{\text{∗}}$$$ с $$$n$$$ вершинами, пронумерованными $$$1, \ldots, n$$$.

Синдаквил проходит по этому дереву и пытается добраться до одного из его листьев$$$^{\text{†}}$$$. Изначально он начинает с не-листовой вершины $$$v$$$, и за один ход он может либо остаться на месте, либо переместиться из вершины $$$v$$$ по ребру к любому из своих соседей $$$u$$$.

Однако Снорлакс пытается помешать Синдаквилу, спя на ребре. Когда он выбирает ребро для сна, Синдаквил не может перемещаться по нему, пока Снорлакс не переместится снова. Более того, в любой момент времени может быть заблокировано только одно ребро, поэтому только последнее выбранное ребро является заблокированным.

Конечно, Снорлакс медленный и ему нужно время, прежде чем он сможет выбрать новое ребро. У него есть таймер перезарядки, изначально равный $$$0$$$. Он может выбрать новое ребро только тогда, когда таймер перезарядки равен $$$0$$$ или меньше, но он не обязан делать это сразу же. Когда он перемещается на новое ребро, таймер становится равным $$$k$$$. После каждого хода Синдаквила(даже если он остается на месте) таймер перезарядки уменьшается на $$$1$$$.

Они ходят поочередно, как описано ранее, начиная со Снорлакса, и изначально все ребра не являются заблокированными. Предполагая, что оба играют оптимально, может ли Синдаквилу всегда добраться до листа за конечное число ходов?

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Вершина с степенью 1 называется листом.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$v$$$ ($$$3 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k, v \leq n$$$) — количество вершин в дереве, таймер перезарядки Снорлакса и начальная вершина Синдаквила.

Следующие $$$n-1$$$ строки каждого набора содержат по два целых числа $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$), описывающие ребро между вершинами $$$a$$$ и $$$b$$$. Гарантируется, что эти ребра образуют дерево и что $$$v$$$ не является листом.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите одну строку, содержащую либо «YES», либо «NO», обозначающую может ли Синдаквил всегда добраться до листа за конечное число ходов или нет.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Пример
Входные данные
6
6 2 1
1 2
2 3
2 4
1 5
5 6
7 1 4
1 2
2 3
3 4
4 5
5 6
6 7
3 1 3
1 3
2 3
4 1 4
1 3
3 4
4 2
9 3 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
9 4 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
Выходные данные
YES
NO
YES
NO
NO
YES
Примечание

В первом наборе входных данных дерево показано ниже:

Синдаквил начинает с вершины $$$1$$$. Если Снорлакс блокирует ребро от $$$1$$$ до $$$2$$$, то Синдаквил может добраться до вершины $$$6$$$ за два хода, что является листом. В противном случае Синдаквил может продвинуться к вершине $$$2$$$, откуда Снорлакс не сможет помешать ему добраться хотя бы до одной из вершин $$$3$$$ и $$$4$$$.

Во втором наборе дерево показано ниже:

Можно показать, что Снорлакс может бесконечно блокировать Синдаквила от достижения листьев $$$1$$$ и $$$7$$$.