Бесси планирует отпуск! Кор-лифония состоит из \(n\) городов, соединенных \(n-1\) двусторонними дорогами. Гарантируется, что из любого города можно добраться до любого другого.
Бесси рассматривает \(v\) возможных планов проведения отпуска, \(i\)-й план описывается начальным городом \(a_i\) и конечным городом \(b_i\).
Известно, что только в \(r\) городах оборудованы специальные стоянки для отдыха. Бесси быстро устает, поэтому не может проехать более чем по \(k\) дорогам подряд, не отдохнув на стоянке. Фактически, отдых для Бесси настолько важен, что она готова ради этого посещать города по несколько раз.
Для каждого плана отпуска, существует ли маршрут для Бесси, который позволит ей добраться из начального города в конечный?
Выходные данные
Если Бесси может достичь конечного города, не проезжая более \(k\) дорог без отдыха подряд, для \(i\)-го плана, выведите YES. Иначе, выведите NO.
Примечание
Граф из первого примера изображен ниже. Города со стоянками для отдыха отмечены красным.
В первом плане, Бесси может посетить следующие города в таком порядке: \(1, 2, 3\).
Во втором плане, Бесси может посетить следующие города в таком порядке: \(3, 2, 4, 5\).
В третьем плане, Бесси не сможет достигнуть конечного города. Например, если она попытается проехать следующим образом: \(3, 2, 4, 5, 6\), ей придется проехать более \(2\) дорог без отдыха.
Граф из второго примера изображен ниже.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 1
1 2
2 3
2 4
4 5
5 6
2
3
1 3
3 5
3 6
|
YES
YES
NO
|
|
2
|
8 3 3
1 2
2 3
3 4
4 5
4 6
6 7
7 8
2 5 8
2
7 1
8 1
|
YES
NO
|