Задача №115391. Ч+К+С
Вам дано два сильносвязных\(^{\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 \("\) иначе.
В первом тестовом случае можно провести из первого графа во второй граф ребра \((1, 3)\), \((4, 2)\) и из второго в первый ребра \((1, 2)\), \((4, 3)\).
Во втором тестовом случае можно как угодно сопоставить вершинам из первого графа вершины второго графа.
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