Kevin and Stones (Hard Version)
Contest: IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: flows, graphs

This is the hard version of the problem. The difference between the versions is that in this version, you need to output a valid sequence of operations if one exists. You can hack only if you solved all versions of this problem.

Kevin has an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Initially, some vertices contain stones, which Kevin wants to move to new positions.

Kevin can perform the following operation:

- For each stone at $$$u_i$$$, select a neighboring vertex $$$v_i$$$. Simultaneously move each stone from $$$u_i$$$ to its corresponding $$$v_i$$$.

At any time, each vertex can contain at most one stone.

Determine whether a valid sequence of operations exists that moves the stones from the initial state to the target state. Output a valid sequence of operations with no more than $$$2n$$$ moves if one exists. It can be proven that if a valid sequence exists, a valid sequence with no more than $$$2n$$$ moves exists.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n \leq 2000$$$, $$$0\leq m \leq \min(\frac{n(n-1)}{2}, 10^4)$$$) — the number of vertices and edges in the graph.

The second line contains a binary string $$$s$$$ consisting of '0' and '1'. The $$$i$$$-th bit of $$$s$$$ indicates the number of stones on the $$$i$$$-th vertex in the initial state.

The third line contains a binary string $$$t$$$ consisting of '0' and '1'. The $$$i$$$-th bit of $$$t$$$ indicates the number of stones on the $$$i$$$-th vertex in the target state.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u, v \leq n$$$) — an undirected edge between the $$$u$$$-th vertex and the $$$v$$$-th vertex.

It is guaranteed that the graph is simple. There are no self-loops and parallel edges in the graph.

It is guaranteed that the numbers of '1' in $$$s$$$ and $$$t$$$ are the same.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^4$$$.

Output format:
For each test case, on the first line, output "Yes" or "No" to indicate whether a valid sequence of operations exists.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If a valid sequence of operations exists, output a single integer $$$k$$$ ($$$0 \leq k \leq 2n$$$) on the second line, representing the number of operations. Suppose there are $$$c$$$ stones in the initial state. The next $$$k + 1$$$ lines should each contain distinct $$$c$$$ integers, representing the positions of the stones before the operations and after each operation. These positions should satisfy the following:

- The positions of the stones in the first line match the initial state from the input, in any order.
- The positions of the stones in the last line match the target state from the input, in any order.
- For all $$$i$$$ ($$$1\leq i\leq k$$$) and $$$j$$$ ($$$1\leq j\leq c$$$), ensure that the $$$j$$$-th integer in the $$$i$$$-th line and the $$$j$$$-th integer in the $$$(i+1)$$$-th line correspond to adjacent vertices in the graph. In other words, the stone is moved from its previous position to the next.

If there are multiple solutions, print any of them.

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

Example input:
4
2 1
10
01
1 2
11 11
11011001010
01101011100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 1
3 2
110
101
1 2
2 3
3 2
111
111
1 2
2 3

Example output:
Yes
1
1
2
Yes
6
1 2 4 5 8 10
2 3 5 6 9 11
3 2 6 7 10 1
4 3 7 8 11 2
5 2 8 9 1 3
6 3 7 8 2 4
7 2 8 9 3 5
No
Yes
0
1 2 3

Editorial:
Necessary and Sufficient Conditions
First, if $$$s = t$$$, the transformation is trivially feasible. Beyond this trivial case, let us consider the necessary conditions:
• The initial state must allow at least one valid move.
• The target state must allow at least one valid move.
• For every connected component, the number of stones in the initial state must match the number of stones in the target state.
• If a connected component is a bipartite graph, then after a coloring of the graph, the number of stones in each part must also satisfy corresponding constraints.
We can represent a node $$$u$$$ as two separate nodes: $$$(u, 0)$$$ and $$$(u, 1)$$$, corresponding to states reachable in even and odd steps, respectively.
For an undirected edge $$$(u, v)$$$, create directed edges between $$$(u, 0)$$$ and $$$(v, 1)$$$, as well as between $$$(u, 1)$$$ and $$$(v, 0)$$$.
Using this transformation:
• It is sufficient to enumerate whether the target state is reached on an even or odd step.
• For each connected component, count the number of stones and verify that the condition is satisfied.
• The bipartite graph constraint is inherently handled within this framework, eliminating the need for special-case treatment.
The first two conditions, ensuring that the initial and target states allow at least one valid move, can be verified using bipartite graph matching. If a valid matching exists, the conditions are satisfied.
Time Complexity: $$$O(\text{BipartiteMatching}(n, m))$$$, where $$$n$$$ is the number of nodes and $$$m$$$ is the number of edges.
It can be shown that the above conditions are not only necessary but also sufficient. By satisfying these conditions, it is guaranteed that a valid transformation from $$$s$$$ to $$$t$$$ can be constructed.
Non-constructive Proof
This is a simpler, non-constructive proof. Below is a brief outline of the proof idea. Since this proof doesn't provide much help for the construction part, some details are omitted.
The problem can be easily formulated as a network flow problem. You can construct a layered graph where each layer represents one step of stone movement, and the flow represents the movement of stones. Determining whether the stones can move from the initial state to the target state is equivalent to checking whether the flow is saturated.
Let $$$c$$$ represent the number of stones. According to the Max-flow Min-cut Theorem, we need to consider whether there exists a cut with a capacity smaller than $$$c$$$.
If we sort all the cut edges by their layer indices, there must exist two adjacent cut edges whose layers, or their distance from the source or sink, exceed $$$n$$$. To disconnect the graph, one of these two regions must fully disconnect the graph. Otherwise, after $$$n$$$ layers, the graph will remain connected. However, since there exists a valid matching between the initial and target states, it is possible to repeatedly move along this matching. This ensures that there exists a flow of size $$$c$$$ from the source or sink to any layer, meaning that the graph cannot be disconnected using fewer than $$$c$$$ edges.
Constructive Proof
Transforming the Graph into a Tree
In the graph after splitting the nodes, if we combine the matching edges from $$$s$$$ and $$$t$$$, we obtain a structure consisting of chains and cycles. Note that for any cycle, the $$$s$$$ and $$$t$$$ edges alternate, meaning we can always adjust the matching of $$$t$$$ in this cycle to make it identical to $$$s$$$.
Afterward, we can find a spanning tree among the remaining edges.
This spanning tree still satisfies both the existence of matching and connectivity conditions. Moreover, all stones in $$$s$$$ and $$$t$$$ (after coloring the graph with black and white) will reside on the same layer.
Solving the Tree Case
For trees, it seems straightforward to move stones outward for subtrees with more stones and inward for subtrees with fewer stones. However, due to the constraint that each step must involve movement, deadlock situations may arise, making it less trivial.
For example, consider the following scenario:
After the first move, $$$S$$$ shifts to positions $$$2$$$ and $$$6$$$. If we only consider the number of stones in the subtrees of $$$s$$$ and $$$t$$$ or simply match based on the shortest distance, the stones might return to $$$1$$$ and $$$5$$$, leading to a deadlock. The correct sequence of moves should be $$$2 \to 3$$$, $$$6 \to 5$$$, then $$$\to 4, 2$$$, and finally $$$\to 3, 1$$$.
Since $$$s$$$ and $$$t$$$ are symmetric, a meet-in-the-middle approach can be applied, where we simultaneously consider both $$$s$$$ and $$$t$$$ and aim to transform them into identical states.
• First find the matching for $$$s$$$ and $$$t$$$.
• The idea is to identify the "outermost" matching edge (the definition of "outermost" will be formalized below). WLOG, we assume it is $$$(t_u, t_v)$$$ in $$$t$$$.
• Then, locate the nearest matching edge $$$(s_u, s_v)$$$ in $$$s$$$ relative to $$$(t_u, t_v)$$$. Move the stones from $$$(s_u, s_v)$$$ to the corresponding nodes in $$$t$$$. Once they reach $$$(t_u, t_v)$$$, let them move back and forth between $$$t_u$$$ and $$$t_v$$$.
• For the remaining unmatched nodes in $$$s$$$, let them oscillate along their own matching edges for the first two steps.
• If the "outermost" matching edge is in $$$s$$$, we can perform the corresponding operations in reverse order.
The explanation of how it works:
• First, since we are choosing the nearest matching edge in $$$s$$$, and the remaining stones move along their matching edges for the first two steps. The remaining stones will not meet the path corresponding to $$$s$$$. Otherwise, it would contradict the definition of "nearest".
• After moving $$$s$$$ to $$$t$$$, the stones will repeatedly move along the matching edge $$$(t_u, t_v)$$$ until the end of the process. This means $$$(t_u, t_v)$$$ becomes impassable for subsequent moves. Therefore, we require this edge to be "outermost," meaning that after removing these two nodes, the remaining parts of $$$s$$$ and $$$t$$$ must still be connected. To find the "outermost" edge, we can iteratively remove the leaf nodes of the graph (nodes with degree at most 1). The first matching edge where both nodes are removed is the "outermost" edge. Note that this "outermost" criterion must consider both $$$s$$$ and $$$t$$$, taking the "outermost" edge among all matches in $$$s$$$ and $$$t$$$.
For the remaining stones, since we ensure the process does not encounter this path or $$$(t_u, t_v)$$$, the problem reduces to a subproblem, which can be solved using the same method.
This approach takes two steps each time and removes one matching edge. If the tree has $$$N = 2n$$$ nodes, the number of matching edges will not exceed $$$n$$$, so we can solve the problem in at most $$$2n$$$ steps.
Time complexity: $$$O(\text{BipartiteMatching}(n, m) + n^2)$$$.
Note: The bound of $$$2n$$$ is tight. For example, consider a chain with an additional triangular loop at the tail. If the goal is to move from $$$1, 2$$$ to $$$1, 3$$$, at least one stone must traverse the triangular loop to change its parity. This requires at least $$$2n - O(1)$$$ steps.