她尽最大努力完美地完成一个人的最后仪式,维护世界的阴阳平衡。
胡涛这个小恶作剧,就用这个图题来吓唬你!给定一个由 $$$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
注意
这是第一个测试用例的查询(红色对应于第一个查询,蓝色对应于第二个查询,绿色对应于第三个查询):
第二个测试用例中的图表如下所示: