Вам даны два сильно связных\(^{\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» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных можно провести из первого графа во второй граф рёбра \((1, 3)\) и \((4, 2)\) (первое число в паре — номер вершины в первом графе, второе число в паре — номер вершины во втором графе), а из второго графа в первый граф провести рёбра \((1, 2)\), \((4, 3)\) (первое число в паре — номер вершины во втором графе, второе число в паре — номер вершины в первом графе).
Во втором наборе входных данных всего есть \(4\) входящих вершины и \(2\) исходящих, поэтому нельзя провести \(3\) рёбер.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|