给你两个强连通的$$$^{\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$$$。
输出
对于每个测试用例,如果可以绘制 $$$n$$$ 新边以满足所有条件,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #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
输出 #1
YES NO YES
注意
在第一个测试用例中,可以从第一个图到第二个图绘制边为 $$$(1, 3)$$$ 和 $$$(4, 2)$$$(对中的第一个数字是第一个图中的顶点编号,对中的第二个数字是第二个图中的顶点编号),从第二个图到第一个图的绘制边为 $$$(1, 2)$$$, $$$(4, 3)$$$(对中的第一个数字是第二个图中的顶点编号,对中的第二个数字是第一个图中的顶点编号)。
在第二个测试用例中,总共有 $$$4$$$ 个传入顶点和 $$$2$$$ 个传出顶点,因此无法绘制 $$$3$$$ 边。