Codeforces Round 980 (Div. 1) |
---|
Finished |
You are given two strongly connected$$$^{\dagger}$$$ directed graphs, each with exactly $$$n$$$ vertices, but possibly different numbers of edges. Upon closer inspection, you noticed an important feature — the length of any cycle in these graphs is divisible by $$$k$$$.
Each of the $$$2n$$$ vertices belongs to exactly one of two types: incoming or outgoing. For each vertex, its type is known to you.
You need to determine whether it is possible to draw exactly $$$n$$$ directed edges between the source graphs such that the following four conditions are met:
$$$^{\dagger}$$$A strongly connected graph is a graph in which there is a path from every vertex to every other vertex.
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$) — the number of vertices in each graph and the value by which the length of each cycle is divisible.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$). If $$$a_i = 0$$$, then vertex $$$i$$$ of the first graph is incoming. If $$$a_i = 1$$$, then vertex $$$i$$$ of the first graph is outgoing.
The third line of each test case contains a single integer $$$m_1$$$ ($$$1 \le m_1 \le 5 \cdot 10^5$$$) — the number of edges in the first graph.
The next $$$m_1$$$ lines contain descriptions of the edges of the first graph. The $$$i$$$-th of them contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — an edge in the first graph leading from vertex $$$v_i$$$ to vertex $$$u_i$$$.
Next, in the same format, follows the description of the second graph.
The next line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i \in \{0, 1\}$$$). If $$$b_i = 0$$$, then vertex $$$i$$$ of the second graph is incoming. If $$$b_i = 1$$$, then vertex $$$i$$$ of the second graph is outgoing.
The next line contains a single integer $$$m_2$$$ ($$$1 \le m_2 \le 5 \cdot 10^5$$$) — the number of edges in the second graph.
The next $$$m_2$$$ lines contain descriptions of the edges of the second graph. The $$$i$$$-th of them contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — an edge in the second graph leading from vertex $$$v_i$$$ to vertex $$$u_i$$$.
It is guaranteed that both graphs are strongly connected, and the lengths of all cycles are divisible by $$$k$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is guaranteed that the sum of $$$m_1$$$ and the sum of $$$m_2$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, output "YES" (without quotes) if it is possible to draw $$$n$$$ new edges such that all conditions are met, and "NO" (without quotes) otherwise.
You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).
34 21 0 0 141 22 33 44 11 0 0 141 33 22 44 13 30 0 031 22 33 11 1 031 22 33 14 21 1 1 141 22 33 44 10 0 0 061 22 11 33 11 44 1
YES NO YES
In the first test case, it is possible to draw edges from the first graph to the second graph as $$$(1, 3)$$$ and $$$(4, 2)$$$ (the first number in the pair is the vertex number in the first graph, and the second number in the pair is the vertex number in the second graph), and from the second graph to the first graph as $$$(1, 2)$$$, $$$(4, 3)$$$ (the first number in the pair is the vertex number in the second graph, and the second number in the pair is the vertex number in the first graph).
In the second test case, there are a total of $$$4$$$ incoming vertices and $$$2$$$ outgoing vertices, so it is not possible to draw $$$3$$$ edges.
Name |
---|