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