그래미 정렬

그래미는 정점 $n$개로 이루어진 연결된 무방향 그래프 $G$를 가지고 있다. 정점은 $1, 2, \ldots, n$으로 번호가 매겨져 있다. 그중 두 정점 $A$와 $B$는 특별한 정점이다. 각 정점 $i$에는 수 $p\_i$가 적혀 있고, $p\_1, p\_2, \ldots, p\_n$은 $1, 2, \ldots, n$의 순열이다.

그래미는 정점에 적힌 수들이 너무 뒤죽박죽이라고 생각한다. 그래서 각 정점 $x$에 대해 다음 조건을 모두 만족하는 경로가 존재하도록 수들을 재배열하려고 한다.

• 경로는 $A$에서 시작해서 $B$에서 끝난다.
• 경로는 정점 $x$를 지난다.
• 경로를 따라 적힌 수가 엄격하게 증가한다.

한 번의 연산에서 그래미는 $A$에서 시작해 임의의 정점에서 끝나는 단순 경로만 고를 수 있다. 그다음 그 경로 위의 수들을 시작점 방향으로 한 칸씩 당기고, 맨 앞의 수는 맨 뒤로 보낸다. 정식으로 말하면, 선택한 단순 경로의 정점에 시작부터 끝까지 $a_1, a_2, \ldots, a_{k-1}, a_k$가 적혀 있다면, 연산 후에는 이 정점들에 $a_2, a_3, \ldots, a_k, a_1$이 적힌다.

그래미는 연산을 최대 $10\,000$번까지만 할 수 있다. 요구한 대로 수를 재배열할 수 있는지 판단하고, 가능하다면 해법을 출력하라.

첫 줄에 네 개의 정수 $n$, $m$, $A$, $B$ ($2 \leq n \leq 1000$, $1 \leq m \leq 2000$, $1 \leq A, B \leq n$, $A \neq B$)가 주어진다.

둘째 줄에는 $n$개의 정수 $p\_1, p\_2, \ldots, p\_n$ ($1 \leq p\_i \leq n$)이 주어진다. $p\_1, p\_2, \ldots, p\_n$은 순열임이 보장된다.

이어지는 $m$개의 줄에는 각각 두 정수 $u\_i$와 $v\_i$ ($1 \leq u\_i, v\_i \leq n$, $u\_i \neq v\_i$)가 주어지며, 이는 $u\_i$와 $v\_i$ 사이에 양방향 간선이 있다는 뜻이다. 그래프는 연결되어 있으며, 임의의 두 정점 사이에 간선은 최대 하나만 있다.

요구한 대로 수를 재배열할 수 없다면 -1을 출력한다.

그렇지 않다면 첫 줄에 연산 횟수 $op$ ($0 \leq op \leq 10\,000$)를 출력한다. 이어지는 $op$개의 줄에는 선택한 단순 경로의 정점 수 $k$를 출력하고, 이어서 경로의 정점 $x_1, x_2, \ldots, x_k$ ($x_1 = A$, $1 \leq x_i \leq n$)를 출력한다. $x_i$는 서로 달라야 하며, $G$에서 경로를 이루어야 한다.

$op$를 최소화할 필요는 없다. 여러 해가 있다면 그중 아무것이나 출력하면 된다.