Moment of Bloom
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 2200
Tags: constructive algorithms, dfs and similar, graph matchings, graphs, greedy, trees

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$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
Here is what the queries look like for the first test case (red corresponds to the 1st query, blue 2nd query, and green 3rd query):

The graph in the second test case looks like this:

Example input:
6 7
2 1
2 3
3 5
1 4
6 1
5 6
4 5
3
1 4
5 1
4 5

Example output:
YES
2
1 4
4
5 3 2 1
5
4 1 2 3 5

Example input:
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

Example output:
NO
2

Editorial:
Let $$$f_v$$$ be the number of times $$$v$$$ appears in the $$$q$$$ queries. If $$$f_v$$$ is odd for any $$$1 \leq v \leq n$$$, then there does not exist an assignment of paths that will force all even edge weights. To see why, notice that one query will correspond to exactly one edge adjacent to $$$v$$$. If an odd number of paths are adjacent to $$$v$$$, this implies that at least one edge adjacent to $$$v$$$ will have an odd degree.
It turns out that this is the only condition that we need to check. In other words, if $$$f_v$$$ is even for all $$$v$$$, then there will exist an assignment of paths that will force all edge weights to be even.
Let's assume all $$$f_v$$$ is even. We can find a solution by doing the following: take any spanning tree of the graph and assign each query to be the path from $$$a$$$ to $$$b$$$ in this tree.
An intuitive way of thinking about this is the following. Consider the case if the spanning tree is a line. Then each query becomes a range and we're checking if all points in this range are covered an even number of times. For all points to be covered an even number of times, every point should occur an even number of times in the queries. To generalize this to a tree, when the first path $$$a_1$$$ to $$$b_1$$$ is incremented, in order to make these values even again, we will need later paths to also overlap the segment from $$$a_1$$$ to $$$b_1$$$. One way this can be done is if we use two paths $$$a_1$$$ to $$$c$$$ and $$$c$$$ to $$$b_1$$$. Notice that even if a new segment that makes the $$$a_1$$$ to $$$b_1$$$ path even makes some other edges odd, the later queries will always fix these edges.