CF1583E.Moment of Bloom

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

她竭尽全力完美地完成一个人的临终仪式，以维系世间阴阳的平衡。

身为小捣蛋鬼的胡桃，试图用这道图论题来吓唬你！你被给定一个包含 $n$ 个节点、$m$ 条边的连通无向图。此外，你还有 $q$ 个查询。每个查询由两个节点 $a$ 和 $b$ 组成。

初始时，图中所有边的权重均为 $0$。对于每个查询，你必须选择一条从 $a$ 出发、到 $b$ 结束的简单路径；然后将该路径上每条边的权重加 $1$。请判断：在处理完全部 $q$ 个查询后，图中所有边的权重是否可能均为偶数。若可能，请输出每个查询所选的路径。

若不可能，请确定最少需额外添加多少个查询才能使其成为可能。可以证明，在给定约束下，该最小数目不会超过 $10^{18}$。

简单路径定义为任意不重复访问同一节点的路径。

当一条边的权值能被 $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$.

第一行包含两个整数 $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$。

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.

如果可以强制使所有边的权重均为偶数，则在第一行输出“YES”，随后输出 $2q$ 行，按查询给出的顺序，依次表示每个查询所选择的路径。对于每个查询，第一行应包含一个整数 $x$：所选路径中的节点数；下一行应包含 $x$ 个用空格分隔的整数 $p_i$，表示所选路径（其中 $p_1 = a$，$p_x = b$，且所有数字均应在 $1$ 到 $n$ 之间）。该路径不能包含重复节点，且必须是图中一条合法的简单路径。

如果无法强制使所有边的权重均为偶数，则在第一行输出“NO”，第二行输出所需额外添加的最少查询数量。

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):

Notice that every edge in the graph is part of either $0$ or $2$ colored query edges.

The graph in the second test case looks like this:

There does not exist an assignment of paths that will force all edges to have even weights with the given queries. One must add at least $2$ new queries to obtain a set of queries that can satisfy the condition.

第一个测试用例的查询如下图所示（红色对应第 1 次查询，蓝色对应第 2 次查询，绿色对应第 3 次查询）：

注意：图中的每条边恰好属于 $0$ 条或 $2$ 条带颜色的查询边。

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

不存在一种路径分配方案，使得在给定查询下所有边的权重均为偶数。必须至少添加 $2$ 个新查询，才能得到一组满足该条件的查询。