Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно только найти только одну из возможных вершин, которую может выбрать Чирно. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Чирно и Дайёсей играют в игру с деревом\(^{\text{∗}}\) из \(n\) вершин, корнем которого является вершина \(1\). Значение \(i\)-й вершины равно \(w_i\). Они по очереди делают ходы; первым ходит Чирно.
На каждом ходу, предполагая, что противник выбрал \(j\) на последнем ходу, игрок может выбрать любую оставшуюся вершину \(i\), удовлетворяющую условию \(w_i>w_j\), и удалить поддерево\(^{\text{†}}\) вершины \(i\). В частности, Чирно может выбрать любую вершину и удалить её поддерево на первом ходу.
Первый игрок, который не может сделать ход, выигрывает, и они оба надеются победить. Найдите одну из возможных вершин, которую может выбрать Чирно на первом ходу, чтобы выиграть, если оба игрока будут играть оптимально.
Выходные данные
Для каждого набора входных данных выведите одну строку.
Если Чирно может выиграть, выведите любую вершину, которую она может выбрать на первом ходу.
В противном случае выведите «0» (без кавычек).
Примечание
В первом наборе входных данных:
- Если Чирно выберет \(1\) или \(3\) на первом ходу, Дайёсей не сможет сделать ход, поэтому Дайёсей выигрывает.
- Если Чирно выберет \(2\) или \(4\) на первом ходу, Дайёсей сможет выбрать только \(3\), но после этого Чирно не сможет сделать ход, поэтому Чирно выигрывает.
Таким образом, все возможные вершины, которые может выбрать Чирно — это \(2\) и \(4\).
Во втором наборе входных данных, независимо от того, какую вершину выберет Чирно, Дайёсей не сможет сделать ход, поэтому Дайёсей выигрывает.
В третьем и четвертом наборах входных данных единственной возможной вершиной, которую может выбрать Чирно на первом ходу, является \(2\).
В пятом наборе входных данных все возможные вершины, которые может выбрать Чирно на первом ходу — это \(3,4,6,7\) и \(10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
2 2 4 3
1 2
1 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 2 3
1 2
1 3
5
3 1 3 4 5
1 2
2 3
3 4
4 5
10
1 2 3 2 4 3 3 4 4 3
1 4
4 6
7 4
6 9
6 5
7 8
1 2
2 3
2 10
|
2
0
2
2
10
|