题目描述

N 国有 $n$ 座城市，城市之间有 $m$ 条双向道路相连。

N 国有三家大型物流公司，每家公司分管一些城市，使得每座城市恰好被一家公司分管。

现在每家公司需要从其分管的城市中选择一些城市建立物流中心，方便货物在城市之间的运输。

但是，由于全国机动车数量实在太多，为改善交通状况，国家不得不采取限行措施。限行措施共有 种，在每种措施中，都会有一家物流公司分管的全部城市禁止外市机动车出入。

显然，限行当天对于被限行的这家物流公司来说将几乎无法开展业务；不仅如此，其他两家公司的业务也好不到哪里去——如果一座自己分管的城市既不是物流中心，也无法通过道路在不经过被限行的城市的情况下到达任何一个自己公司的物流中心，这座城市当天的物流就会受到很大影响。

因此，每家公司在选择物流中心时都会慎重考虑，避免这种情况的发生。

具体来说，不妨设这三家物流公司是 $1$ 号、$2$ 号和 $3$ 号，则对于公司 $1$ 而言，他们选择的物流中心需要保证：当公司 $2$ 的城市被限行时，任何一个公司 $1$ 的城市都能通过道路在不经过公司 $2$ 的城市时到达公司 $1$ 的某一个物流中心；当公司 $3$ 的城市被限行时情况也是类似的。同样，对于公司 $2$ 和公司 $3$ 而言，选择物流中心的要求也是类似的。

由于建立一座物流中心的花费是很高的，他们都希望自己选择的城市越少越好。

现在请你给出一种三家公司选择物流中心的方案。

输入格式

第一行：两个正整数 $n,m$。

第二行：$n$ 个正整数 $a_i$，表示城市 $i$ 归属的公司，满足 $a_i\in \{1,2,3\}$。保证每个物流公司至少管辖一座城市。

接下来 $m$ 行：每行两个正整数 $u_i,v_i$，表示一条连接城市 $u_i$ 和 $v_i$ 的道路。保证无重边自环。

输出格式

输出共三行，分别表示公司 $1$、$2$、$3$ 的一种选择物流中心的方案。

对于第 $i$ 行而言，先输出一个正整数 $k_i$ 表示公司 $i$ 最少选择的物流中心数目；紧接着输出 $k_i$ 个互不相同的正整数表示一种选择 $k_i$ 个物流中心的方案，，要求这些城市都是归属公司 $i$ 管辖的，具体输出顺序任意。

如果有多种符合题意的方案的城市数目并列最少，只需输出任意一种即可。

样例

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

2 1 5
1 2
1 4

数据范围

• 对于 $10\%$ 的数据，$n\le 20$，$m\le 50$。
• 对于 $30\%$ 的数据，$n\le 200$，$m\le 500$。
• 对于 $60\%$ 的数据，$n\le 3\times 10^3$，$m\le 10^4$。
• 对于 $100\%$ 的数据，$n\le 10^5$，$m\le 2\times 10^5$，$1\le u_i,v_i\le n$。