Grammy Sorting

Grammy has a connected undirected graph $G$ with $n$ vertices numbered $1, 2, \ldots, n$. Among them are two special vertices $A$ and $B$. Each vertex $i$ has a number $p\_i$ written on it, where $p\_1, p\_2, \ldots, p\_n$ is a permutation of $1, 2, \ldots, n$.

Grammy thinks the numbers on the vertices are too chaotic. She wants to reorder them so that, for each vertex $x$, there is a path that satisfies all of the following:

• The path starts at $A$ and ends at $B$.
• The path contains vertex $x$.
• The numbers along the path are strictly increasing.

In each operation, Grammy can only choose a simple path that starts at $A$ and ends at an arbitrary vertex. She then shifts the numbers on that path one position toward the start and moves the first number to the last position. Formally, if the vertices on the chosen simple path hold numbers $a_1, a_2, \ldots, a_{k-1}, a_k$ from start to end, then after the operation they hold $a_2, a_3, \ldots, a_k, a_1$.

Grammy can perform no more than $10\,000$ operations. Determine whether she can reorder the numbers as required. If she can, output a solution.

The first line contains four integers $n$, $m$, $A$, $B$ ($2 \leq n \leq 1000$, $1 \leq m \leq 2000$, $1 \leq A, B \leq n$, $A \neq B$).

The second line contains $n$ integers $p\_1, p\_2, \ldots, p\_n$ ($1 \leq p\_i \leq n$). It is guaranteed that $p\_1, p\_2, \ldots, p\_n$ is a permutation.

Each of the next $m$ lines contains two integers $u\_i$ and $v\_i$ ($1 \leq u\_i, v\_i \leq n$, $u\_i \neq v\_i$), meaning there is a bidirectional edge between $u\_i$ and $v\_i$. The graph is connected, and there is at most one edge between any pair of vertices.

If Grammy cannot reorder the numbers as required, output -1.

Otherwise, output an integer $op$ ($0 \leq op \leq 10\,000$) on the first line, the number of operations. On each of the next $op$ lines, output an integer $k$, the number of vertices on the chosen simple path, followed by $k$ integers $x_1, x_2, \ldots, x_k$ ($x_1 = A$, $1 \leq x_i \leq n$), the vertices of the path. The $x_i$ must be distinct and form a path in $G$.

You do not need to minimize $op$. If there are multiple solutions, output any one of them.