Statement is not available in English language
H. Ч+К+С
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

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

Вторая строка каждого набора входных данных содержит последовательность из $$$n$$$ чисел, каждое из которых $$$0$$$, либо $$$1$$$ — классы вершин первого графа. Если $$$i$$$-е число в последовательности равно $$$0$$$, значит, $$$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$$$.

Далее в таком же формате вводятся классы вершин второго графа, количество ребер второго графа $$$m_2$$$ и сами ребра второго графа.

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

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

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

Пример
Входные данные
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
4 2
1 1 0 1
4
1 2
2 3
3 4
4 1
1 0 1 1
4
1 3
3 2
2 4
4 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)$$$.

Во втором тестовом случае можно как угодно сопоставить вершинам из первого графа вершины второго графа.