CF2023C.C+K+S

给您两个强连接 $^{1}$ 有向图，每个图都有恰好 $n$ 个顶点，但可能有不同数量的边。仔细观察后，您发现了一个重要特征--这两个图中任何一个循环的长度都能被 $k$ 整除。

每个 $2n$ 顶点都属于两种类型中的一种：传入或传出。每个顶点的类型都是已知的。

您需要确定是否有可能在源图之间绘制恰好 $n$ 条有向边，从而满足以下四个条件：

• 任何添加的边的两端都位于不同的图中。
• 从每个传出顶点，正好有一条新增边产生。
• 在每个进入的顶点中，正好有一条添加边进入。
• 在生成的图中，任何循环的长度都能被 $k$ 整除。

$^{1}$强连接图是指从每个顶点到其他顶点都有一条路径的图。

每个测试由多个测试用例组成。第一行包含一个整数 $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$ 。

对于每个测试用例，如果可以绘制 $n$ 条新边且满足所有条件，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

您可以输出任何情况下的答案（例如，字符串 "yEs"、"yes"、"Yes "和 "YES "将被视为肯定答案）。

样例解释

在第一个测试用例中，从第一个图到第二个图的边可以绘制为 $(1, 3)$ 和 $(4, 2)$ （这对边中的第一个数字是第一个图中的顶点编号，这对边中的第二个数字是第二个图中的顶点编号），从第二个图到第一个图的边可以绘制为 $(1, 2)$ 和 $(4, 3)$ （这对边中的第一个数字是第二个图中的顶点编号，这对边中的第二个数字是第一个图中的顶点编号）。

在第二个测试案例中，共有 $4$ 个进入顶点和 $2$ 个离开顶点，因此无法绘制 $3$ 条边。