Марсель и Валериу находятся в безумном городе, который представляет собой \(n\) зданий с \(n\) двусторонними дорогами между ними.
Марсель и Валериу начинают в зданиях \(a\) и \(b\) соответственно. Марсель хочет поймать Валериу, то есть оказаться в том же здании, что и он, или встретиться на одной дороге.
Во время каждого хода они выбирают, пойти в соседнее здание от текущего или остаться в том же здании. Поскольку Валериу хорошо знает Марселя, Валериу может предсказать, куда Марсель пойдет в следующем ходу. Валериу может использовать эту информацию, чтобы сделать свой ход. Они начинают и заканчивают ход одновременно.
Гарантируется, что любая пара зданий соединена некоторым путем, и между любой парой зданий есть не более одной дороги.
Предполагая, что оба игрока играют оптимально, ответьте, есть ли у Валериу стратегия, чтобы бесконечно уходить от Марселя.
Выходные данные
Для каждого набора входных данных выведите «YES», если Валериу может бесконечно уходить от Марселя, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
В первом примере граф выглядит следующим образом:
Марсель начинает в здании
\(2\), а Валериу начинает в здании
\(1\). Валериу знает, каким путем Марсель будет двигаться вокруг треугольника, и он может просто всегда двигаться так же, чтобы всегда избегать Марселя.
Во втором примере граф выглядит следующим образом:
Марсель начинает в здании
\(1\), а Валериу начинает в здании
\(4\). Марсель может пойти в здание
\(4\) на своем первом ходу и победить, так как Валериу должен либо пойти в здание
\(1\) (тогда они встретятся на дороге от
\(1\) до
\(4\)), либо остаться в здании
\(4\) (тогда они встретятся в здании
\(4\)). Таким образом, у Валериу нет стратегии для победы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2 1
2 1
3 2
1 3
4 1 4
1 4
1 2
1 3
2 3
4 1 2
1 2
2 3
2 4
3 4
7 1 1
4 1
2 1
5 3
4 6
4 2
7 5
3 4
8 5 3
8 3
5 1
2 6
6 8
1 2
4 8
5 7
6 7
10 6 1
1 2
4 3
5 8
7 8
10 4
1 9
2 4
8 1
6 2
3 1
|
YES
NO
YES
NO
NO
YES
|