← 返回题目列表

Codeforces · 2023/C

C. C、K与S之和

中文机器翻译题面 查看原题

给你两个强连通的$$$^{\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$$$ 边。