Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Statement is not available in English language
D. Я больше никогда не буду играть в Minecraft
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы уже с другом уже третий день играете в Minecraft, возводя грандиозные здания, путешествуя между вселенными и ни разу не выходя из дома. Чтобы сделать игру еще более увлекательной, вы решили довериться схеме из интернета и построить портал в MysteryUniverse503, но что-то пошло не по плану, и вы с другом телепортируетесь в SecretWorld404.

Известно, что вторгаться на чужую территорию без спроса - плохо, поэтому либо вы, либо ваш друг понесут серьезное наказание. Чтобы определить, кто из вас останется играть, а кто с позором уйдет на новую карту, вы решили сыграть в игру, которую нашли в зачарованной книге.

Правила игры гласят, что игра ведется на слабо-связном ориентированном$$$^{*}$$$ ациклическом графе из $$$n$$$ вершин, в каждой из которых находится либо сундук, либо верстак, и $$$m$$$ рёбер. Вы с другом будете ходить по очереди, вы ходите первым.

Во время хода нужно выбрать одну из вершин, в которой лежит сундук, и число $$$k$$$, после чего поменять предмет на противоположный (сундук на верстак или верстак на сундук) во всех вершинах, до которых от выбранной можно добраться за $$$\le k$$$ ходов (включая выбранную). Если оказывается так, что во всех вершинах графа находится верстак, то игрок, который сейчас должен делать ход ход, проигрывает.

Требуется определить, кто станет победителем и останется играть в SecretWorld404, если вы с другом играете оптимально.

$$$^{*}$$$Слабо-связный ориентированный граф - ориентированный граф, который станет связным, если убрать направление ребер.

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

В первой строке находятся два числа — количество вершин в графе $$$n$$$ ($$$1 \le n \le 10^4$$$) и количество рёбер $$$m$$$ ($$$n - 1 \le m \le 10^4$$$).

На следующей строке находится $$$n$$$ целых чисел $$$c_i$$$ ($$$0 \le c_i \le 1$$$), определяющих предмет в вершине. Если $$$c_i = 0$$$, то в вершине $$$i$$$ находится верстак, иначе сундук.

Каждая из следующих $$$m$$$ строк содержит номера двух вершин $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), соединенных ребром из $$$u_i$$$ в $$$v_i$$$.

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

Выведите одно число: $$$1$$$, если победителем станете вы, или $$$2$$$, если выиграет ваш друг.

Система оценки
ГруппаДополнительные ограниченияБаллыЗависит от
$$$1$$$$$$n \le 20, m \le 100$$$$$$13$$$–
$$$2$$$Из вершин с сундуком не исходит рёбер$$$9$$$–
$$$3$$$Все рёбра исходят из одной вершины, $$$m = n - 1$$$$$$11$$$–
$$$4$$$Вершины можно разбить на две доли так,
чтобы все рёбра шли из первой доли во вторую$$$17$$$$$$3$$$
$$$5$$$$$$n, m \le 500$$$$$$19$$$$$$1$$$
$$$6$$$$$$n, m \le 10^4$$$$$$31$$$$$$1-5$$$
Примеры
Входные данные
4 3
1 1 1 0
1 3
2 3
2 4
Выходные данные
1
Входные данные
5 5
1 0 1 1 0
1 2
2 3
2 4
3 4
3 5
Выходные данные
1
Входные данные
5 4
0 1 1 0 1
5 4
4 3
3 2
2 1
Выходные данные
1
Примечание

Обратите внимание: в графе могут присутствовать кратные рёбра.