• 来源：43rd Petrozavodsk Programming Camp, Summer 2022, Day 2: ZJU Contest 1, Problem H. Grammy Sorting
• 时间限制：1 second
• 空间限制：256 mebibytes

题目描述

Grammy 手里有一张连通的无向星路图 $G$，共有 $n$ 个点，编号为 $1,2,\ldots,n$。其中有两个特殊点 $A$ 与 $B$。每个点 $i$ 上写着一个数字 $p_i$，并且 $p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。

Grammy 希望重新排列这些点上的数字，使得对于每一个点 $x$，都存在一条路径满足：

• 这条路径从 $A$ 出发，到 $B$ 结束；
• 这条路径经过点 $x$；
• 沿路径依次看到的数字严格递增。

她能进行的操作受到很大限制。一次操作中，Grammy 只能选择一条从 $A$ 出发、到任意一个点结束的简单路径，然后把路径上的数字整体向起点方向循环移动一格，并把原本位于起点的数字放到路径末端。

形式化地说，若所选简单路径从起点到终点依次经过的点上写着

那么操作后这些点上的数字会变成

Grammy 最多只能执行 $10000$ 次操作。

请判断是否能够通过不超过 $10000$ 次操作达到要求。如果可以，请输出任意一种操作方案；如果不可以，请输出 -1。

输入格式

第一行包含四个整数 $n,m,A,B$。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$。保证它们构成 $1,2,\ldots,n$ 的一个排列。

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示点 $u_i$ 与点 $v_i$ 之间有一条无向边。

保证图连通，且任意两点之间至多有一条边。

输出格式

如果无法完成重排，输出一行 -1。

否则，第一行输出一个整数 $op$，表示操作次数。

接下来 $op$ 行，每行先输出一个整数 $k$，表示本次选择的简单路径包含的点数；随后输出 $k$ 个整数 $x_1,x_2,\ldots,x_k$，表示这条路径上的点。

输出的路径必须满足：

• $x_1=A$；
• $1\le x_i\le n$；
• $x_1,x_2,\ldots,x_k$ 两两不同；
• 相邻两个点在图 $G$ 中有边相连。

可以证明：如果存在可行重排，则一定存在一种操作次数不超过 $10000$ 的方案。

你不需要最小化 $op$。若有多种方案，输出任意一种即可。

数据范围

• $2\le n\le 1000$；
• $1\le m\le 2000$；
• $1\le A,B\le n$；
• $A\ne B$；
• $1\le p_i\le n$；
• $0\le op\le 10000$。

样例 1

输入

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

样例 2

输入

4 3 1 2
1 4 2 3
1 4
2 4
3 4

输出

-1