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$ 条边。

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.