8573: Grammy Sorting

链接：https://ac.nowcoder.com/acm/contest/33192/H
来源：牛客网
Grammy has a connected undirected graph $G$ with two special vertices $A$ and $B$. Each of the vertices has a number pip_ipi written on it, where p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn is a permutation of size $n$. 

Grammy thinks these numbers on vertices are too chaotic. She wants to reorder the numbers such that for each vertex $x$, there exists a path satisfying the following conditions: 

1. The path starts from $A$ and ends at $B$. 

2. The path contains vertex $x$. 

3. The numbers along the path are strictly increasing. 

Sadly, in each operation, Grammy can only choose a simple path starting from $A$ and ending at an arbitrary vertex, then shift the numbers on the simple path by 1. That is, if the vertices on the simple path chosen by Grammy contains a1,a2,…,ak−1,aka_1, a_2, \dots,a_{k-1}, a_ka1,a2,…,ak−1,ak, then after Grammy's operation, these vertices will become a2,a3,…,ak,a1a_2, a_3, \dots, a_k, a_1a2,a3,…,ak,a1. 

Additionally, Grammy can only operate no more than $10000$ times. 

Grammy cannot find out any plan to solve this problem, so she asked you for help. 

Please help Grammy to determine whether she can reorder the numbers. You also need to output a solution if it exists. 

The first line contains $4$ integers n,m,A,Bn,m,A,Bn,m,A,B (2≤n≤1000,1≤m≤2000,1≤A,B≤n,A≠B2\leq n \leq 1\,000, 1 \leq m \leq 2\,000, 1 \leq A,B \leq n, A \neq B2≤n≤1000,1≤m≤2000,1≤A,B≤n,A=B). 
The second line contains $n$ integers p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn (1≤pi≤n1 \leq p_i \leq n1≤pi≤n). It is guaranteed that p1,p2,…,pnp_1, p_2, \dots, p_np1,p2,…,pn is a permutation. 
In each of the next $m$ lines, there are two integers ui,viu_i, v_iui,vi (1≤ui,vi≤n1 \leq u_i,v_i \leq n1≤ui,vi≤n), denoting that there is a bidirectional edge between uiu_iui and viv_ivi. It is guaranteed that the graph is connected. 

If Grammy cannot properly reorder the numbers, output $-1$ (without quotes). 
Otherwise output an integer $op$ ($0\le op\le 10000$) in the first line, indicating the number of operations Grammy needs. 
For the following $op$ lines, output an integer $k$, denoting the number of vertices on the chosen simple path. Then output $k$ integers x1,x2,…,xkx_1, x_2, \dots, x_kx1,x2,…,xk(x1=A,1≤xi≤nx_1=A, 1 \leq x_i \leq nx1=A,1≤xi≤n), indicating the vertices on the simple path. These xix_ixi should be distinct. 
It can be proved that if graph $G$ can be properly reordered, there exists a solution with no more than $10000$ operations. 
Note that you don't have to minimize $op$. If there are multiple solutions, output any of them. 

5 6 1 2
1 2 3 4 5
1 3
2 3
1 4
2 4
1 5
3 5

7
4 1 3 2 4
3 1 3 2
3 1 3 5
4 1 3 2 4
3 1 3 2
2 1 3
1 1