← 返回题目列表

Codeforces · 1583/E

E. 绽放的时刻

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

她尽最大努力完美地完成一个人的最后仪式,维护世界的阴阳平衡。

胡涛这个小恶作剧,就用这个图题来吓唬你!给定一个由 $$$n$$$ 节点和 $$$m$$$ 边组成的无向连通图。您还有 $$$q$$$ 查询。每个查询由两个节点 $$$a$$$ 和 $$$b$$$ 组成。

最初,图中所有边的权重均为 $$$0$$$。对于每个查询,您必须选择一条从 $$$a$$$ 开始并以 $$$b$$$ 结束的简单路径。然后将 $$$1$$$ 添加到这条路径上的每条边上。确定在处理所有 $$$q$$$ 查询后是否可以使该图中的所有边具有均匀的权重。如果是,则输出每个查询的路径选择。

如果不可能,请确定可以添加的最少额外查询数以使其成为可能。可以证明,在给定的约束下,这个数字不会超过$$$10^{18}$$$。

简单路径定义为不会多次访问节点的任何路径。

如果一条边的值可以被 $$$2$$$ 整除,则称该边具有偶数权重。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right)}$$$)。

接下来的 $$$m$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x\neq y$$$),表示节点 $$$x$$$ 和 $$$y$$$ 之间的无向边。输入不会包含自循环或重复边,并且提供的图将被连接。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$)。

接下来的 $$$q$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n, a \neq b$$$),即每个查询的描述。

保证$$$nq \leq 3 \cdot 10^5$$$。

输出

如果可以强制所有边权重均匀,请在第一行打印“YES”,然后是 $$$2q$$$ 行,指示每个查询的路径选择,顺序与给出查询的顺序相同。对于每个查询,第一行应包含一个整数 $$$x$$$:所选路径中的节点数。然后,下一行应包含 $$$x$$$ 间隔分隔的整数 $$$p_i$$$ 指示您所采取的路径($$$p_1 = a,p_x = b$$$ 并且所有数字应位于 $$$1$$$ 和 $$$n$$$ 之间)。该路径不能包含重复节点,并且必须是图中有效的简单路径。

如果无法强制所有边权重均匀,请在第一行打印“NO”,并在第二行打印添加的查询的最小数量。

示例

输入 #1

6 7
2 1
2 3
3 5
1 4
6 1
5 6
4 5
3
1 4
5 1
4 5

输出 #1

YES
2
1 4
4
5 3 2 1
5
4 1 2 3 5

输入 #2

5 7
4 3
4 5
2 1
1 4
1 3
3 5
3 2
4
4 2
3 5
5 1
4 5

输出 #2

NO
2

注意

这是第一个测试用例的查询(红色对应于第一个查询,蓝色对应于第二个查询,绿色对应于第三个查询):

第二个测试用例中的图表如下所示: