C. Ч+К+С
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два сильно связных$$$^{\dagger}$$$ ориентированных графа, в каждом из которых ровно $$$n$$$ вершин, но может быть разное количество рёбер. Посмотрев на них внимательно, вы заметили важную особенность — длина любого цикла в этих графах делится на $$$k$$$.

Каждая из $$$2n$$$ вершин относится ровно к одному из двух типов: входящая или исходящая. Для каждой вершины вам известен её тип.

Вам нужно определить, можно ли провести ровно $$$n$$$ ориентированных рёбер между исходными графами так, чтобы выполнялись следующие четыре условия:

  • Концы любого добавленного ребра лежат в разных графах.
  • Из каждой исходящей вершины исходит ровно одно добавленное ребро.
  • В каждую входящую вершину входит ровно одно добавленное ребро.
  • В получившемся графе длина любого цикла делится на $$$k$$$.

$$$^{\dagger}$$$Сильно связный граф — это граф, в котором из каждой вершины существует путь до любой другой вершины.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$) — количество вершин в каждом из графов и значение, на которое делится длина каждого цикла.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$). Если $$$a_i = 0$$$, то вершина $$$i$$$ первого графа является входящей. Если $$$a_i = 1$$$, то вершина $$$i$$$ первого графа является исходящей.

Третья строка каждого набора входных данных содержит одно целое число $$$m_1$$$ ($$$1 \le m_1 \le 5 \cdot 10^5$$$) — количество рёбер в первом графе.

Следующие $$$m_1$$$ строк содержат описания рёбер первого графа. $$$i$$$-я из них содержит два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — ребро в первом графе, ведущее из вершины $$$v_i$$$ в вершину $$$u_i$$$.

Далее в таком же формате следует описание второго графа.

Следующая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i \in \{0, 1\}$$$). Если $$$b_i = 0$$$, то вершина $$$i$$$ второго графа является входящей. Если $$$b_i = 1$$$, то вершина $$$i$$$ второго графа является исходящей.

Следующая строка содержит одно целое число $$$m_2$$$ ($$$1 \le m_2 \le 5 \cdot 10^5$$$) — количество рёбер во втором графе.

Следующие $$$m_2$$$ строк содержат описания рёбер второго графа. $$$i$$$-я из них содержит два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — ребро во втором графе, ведущее из вершины $$$v_i$$$ в вершину $$$u_i$$$.

Гарантируется, что оба графа являются сильно связными, а также длины всех циклов кратны $$$k$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Гарантируется, что сумма $$$m_1$$$ и сумма $$$m_2$$$ по всем наборам входных данных не превосходят $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите «YES» (без кавычек), если можно провести $$$n$$$ новых рёбер так, чтобы выполнялись все условия, и «NO» (без кавычек) иначе.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
3
4 2
1 0 0 1
4
1 2
2 3
3 4
4 1
1 0 0 1
4
1 3
3 2
2 4
4 1
3 3
0 0 0
3
1 2
2 3
3 1
1 1 0
3
1 2
2 3
3 1
4 2
1 1 1 1
4
1 2
2 3
3 4
4 1
0 0 0 0
6
1 2
2 1
1 3
3 1
1 4
4 1
Выходные данные
YES
NO
YES
Примечание

В первом наборе входных данных можно провести из первого графа во второй граф рёбра $$$(1, 3)$$$ и $$$(4, 2)$$$ (первое число в паре — номер вершины в первом графе, второе число в паре — номер вершины во втором графе), а из второго графа в первый граф провести рёбра $$$(1, 2)$$$, $$$(4, 3)$$$ (первое число в паре — номер вершины во втором графе, второе число в паре — номер вершины в первом графе).

Во втором наборе входных данных всего есть $$$4$$$ входящих вершины и $$$2$$$ исходящих, поэтому нельзя провести $$$3$$$ рёбер.