Джон Уик оказался втянут в противостояние между старым Правлением и новой фракцией. Исход противостояния определится тем, к какой фракции примкнет сам Джон, но он пока предпочитает сохранять нейтралитет, поэтому ему стоит тщательно планировать свои перемещения.
Карта городов, между которыми Джону может понадобиться перемещаться, представляет собой неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер. Граф не обязательно связный, то есть не обязательно между каждой парой городов есть путь. В каждом городе большее влияние имеет ровно одна из двух фракций.
Джон считает распределение влияния фракций по городам достаточно нейтральным, если в любых двух городах, соединенных ребром, главенствуют разные фракции. Он может подтянуть старые связи и использовать свои Маркеры, чтобы изменить баланс сил в некоторых городах, однако он считает неблагоразумным вмешиваться больше, чем требуется. Всего есть $$$k$$$ городов, на которые Джон может оказать влияние: $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$.
Помогите Джону определить, в каком минимальном количестве городов ему следует поменять влияние одной фракции на другой, чтобы распределение фракций стало нейтральным.
В первой строке входных данных дано два числа $$$n$$$ и $$$m$$$ — количество городов и дорог между ними ($$$1 \leqslant n \leqslant 10^4$$$; $$$1 \leqslant m \leqslant 2 \cdot 10^5$$$).
Во второй строке через пробел даны $$$n$$$ целых чисел, $$$i$$$-е из которых равно $$$1$$$ или $$$2$$$ и означает, какая из двух фракций имеет большее влияние в $$$i$$$-м городе.
В третьей дано через пробел перечислены $$$n$$$ целых чисел, $$$i$$$-е из которых равно $$$0$$$, если Джон не может оказать влияние на $$$i$$$-й город, и $$$1$$$ иначе. Всего среди этих чисел ровно $$$k$$$ единиц.
В последних $$$m$$$ строках заданы дороги между городами: в $$$i$$$-й из строк через пробел даны два целых числа $$$u_i$$$ и $$$v_i$$$ — города, между которыми проведена $$$i$$$-я дорога ($$$1 \leqslant u_i, v_i \leqslant n$$$; $$$u_i \neq v_i$$$). Гарантируется, что все дороги проведены между разными парами городов.
Выведите одно целое число число — минимальное количество городов, в которых требуется изменить главенствующую фракцию, чтобы граф стал нейтральным, либо «-1» (без кавычек), если это невозможно.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 11 | $$$n \leqslant 20$$$ | полная | |
| 2 | 22 | каждый город имеет ровно одну дорогу | первая ошибка | |
| 3 | 16 | $$$k = 0$$$ | первая ошибка | |
| 4 | 24 | $$$k \leqslant 1$$$ | 3 | первая ошибка |
| 5 | 27 | нет | 1 – 4 | первая ошибка |
4 2 1 1 1 2 1 1 1 0 1 2 2 3
1
4 4 1 1 1 1 0 0 1 1 1 2 2 3 3 4 1 4
-1
5 5 1 1 1 2 2 1 1 1 1 0 1 2 2 3 3 4 4 1 4 5
3