“有内鬼，终止计划！”就在仪式开始的一分钟前，粉免的翻盖手机里收到了这样的消息。仪式顺利举行还受到了兔王的称赞的你一脸懵逼。“怎么会这样呢？”意识到粉免可能有同伙的你决定使出杀手锏。

这次你想起了一道传说中的问题。

传说在月亮上住着很多只兔子，兔子有不同的颜色，比如粉兔，红兔，粉红兔，红粉兔…

月亮上有一个拥有 $n$ 个节点 $m$ 条边的无向的交通网络，每个节点上最多住着一只兔子。兔子们可以沿着交通网络里的路径前去拜访其他兔子，然后一起吃月饼。根据同类相斥、异类相吸的原理，兔子只想与其他颜色的兔子做朋友。而兔子是一种高冷的生物，喜欢独来独往，因此它们不希望自己在行程中遇到其他兔子。

传说中粉兔的情商和智商都特别特别高，所以总能规划出一种兔子的出行方案，使得朋友的对数最多。这一规划的过程俗称“找对”。

然而，你发现这传说根本就是在瞎扯，这么困难的问题，粉兔自然是不会做的，因此会做这个问题的只能是粉免。

于是你决定先自己算出最优解，然后再看看谁跟你求的解一致，就能知道谁是粉免啦。

形式化题意：

给一张图 $G=(V,E)$，其中每个点的颜色编号用 $c_i$ 表示，$c_i=0$ 则表示这个点没有颜色。找到最多的简单路径，使得：

1. 没有两条路径相交，这里相交指有节点重合；
2. 每条路径的两端都有颜色且两端颜色不相同。除了两端之外，路径不穿过任何有颜色的节点。

输入格式

第一行两个整数 $n,m$，分别表示点数和边数。

第二行 $n$ 个整数 $c_i$ 表示每个点的颜色。

接下来 $m$ 行，每行两个整数 $x,y$，表示一条边，可能有重边和自环。

输出格式

第一行一个整数 $ans$，表示最多的路径条数。

接下来 $ans$ 行，每行第一个整数 $K_i$ 表示这条路径的点数，接下来 $K_i$ 个整数 $x_i$ 依次表示路径上的点，需要满足 $x_i,x_{i+1}$ 之间有边，且所有路径满足题目条件。

如果有多种合法简单路径安排方案，任意输出一种即可。

样例一

input

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

output

1
3 4 2 1 

explanation

$4-2-1$上的颜色分别为$2-0-3$，合法。

样例二

input

6 8
0 3 0 4 1 0 
1 1
5 3
1 5
1 1
3 4
1 1
4 5
1 5

output

1
2 5 4 

样例三

input

12 20
4 2 1 1 2 2 1 3 1 3 1 3 
7 1
11 7
8 1
5 4
9 8
4 5
4 7
1 5
3 2
1 4
1 11
10 1
1 6
1 2
4 3
11 10
1 9
8 10
12 10
11 8

output

5
2 6 1 
2 3 2 
2 5 4 
2 9 8 
2 11 10 

样例四

见附件下载。

数据范围与提示

对于所有数据，$1⩽n⩽300$，$1⩽m⩽(\genfrac{}{}{0ex}{}{n}{2})$，$0⩽c_i⩽n$。

时间限制：$5\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$