308844: CF1583E. Moment of Bloom
Memory Limit：512 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Moment of Bloom
题意翻译
她尽自己最大的努力，完美地完成一个人的心愿——保持世界的阴阳平衡. HU TAO，这个爱恶作剧的小妖精，居然用这个平衡来吓唬你!给出了一个由m个边的n个节点组成的连通无向世界。你也有q个计划。每个计划由两个节点a和b组成。 最初，世界中所有边的能量都是0。对于每个计划，您必须选择一个从a开始到b结束的简单路径。然后给这条路径上的每条边加上为1大小的能量。在处理完所有q计划后，确定是否有可能使世界中所有边的能量大小都是偶数（0是偶数）。如果是，输出每个计划的路径选择。（可以任意一个解） 简单路径定义：访问节点不超过一次的任何路径。 Ps：如果一条边的值能被2整除，则称其权值为偶数。 输入格式： 2个n m m行:x y//表示x可以和y连 一个q q行:x y//表示x 到y的边加一 输出：一共2*q行 如果可以使所有边的能量为偶数，则在第一行输出“YES”，表示每个计划的路径选择，顺序与给出的计划相同。对于每个计划，第一行应该包含一个整数x:所选路径中的节点数。在第二行输出表示每个计划的路径选择（空格隔开） 如果不可能使所有边的能量为偶数，则在第一行输出 “NO”，在第二行输出添加的计划最小数量。 数据范围：2<=n,m<=3e5 (m>n*(n-1)/2) Q<=3e5题目描述
She does her utmost to flawlessly carry out a person's last rites and preserve the world's balance of yin and yang. Hu Tao, being the little prankster she is, has tried to scare you with this graph problem! You are given a connected undirected graph of $ n $ nodes with $ m $ edges. You also have $ q $ queries. Each query consists of two nodes $ a $ and $ b $ . Initially, all edges in the graph have a weight of $ 0 $ . For each query, you must choose a simple path starting from $ a $ and ending at $ b $ . Then you add $ 1 $ to every edge along this path. Determine if it's possible, after processing all $ q $ queries, for all edges in this graph to have an even weight. If so, output the choice of paths for each query. If it is not possible, determine the smallest number of extra queries you could add to make it possible. It can be shown that this number will not exceed $ 10^{18} $ under the given constraints. A simple path is defined as any path that does not visit a node more than once. An edge is said to have an even weight if its value is divisible by $ 2 $ .输入输出格式
输入格式
The first line contains two integers $ n $ and $ 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)} $ ). Each of the next $ m $ lines contains two integers $ x $ and $ y $ ( $ 1 \leq x, y \leq n $ , $ x\neq y $ ) indicating an undirected edge between node $ x $ and $ y $ . The input will not contain self-loops or duplicate edges, and the provided graph will be connected. The next line contains a single integer $ q $ ( $ 1 \leq q \leq 3 \cdot 10^5 $ ). Each of the next $ q $ lines contains two integers $ a $ and $ b $ ( $ 1 \leq a, b \leq n, a \neq b $ ), the description of each query. It is guaranteed that $ nq \leq 3 \cdot 10^5 $ .
输出格式
If it is possible to force all edge weights to be even, print "YES" on the first line, followed by $ 2q $ lines indicating the choice of path for each query in the same order the queries are given. For each query, the first line should contain a single integer $ x $ : the number of nodes in the chosen path. The next line should then contain $ x $ spaced separated integers $ p_i $ indicating the path you take ( $ p_1 = a, p_x = b $ and all numbers should fall between $ 1 $ and $ n $ ). This path cannot contain duplicate nodes and must be a valid simple path in the graph. If it is impossible to force all edge weights to be even, print "NO" on the first line and the minimum number of added queries on the second line.
输入输出样例
输入样例 #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