“有内鬼,终止计划!”就在仪式开始的一分钟前,粉免的翻盖手机里收到了这样的消息。仪式顺利举行还受到了兔王的称赞的你一脸懵逼。“怎么会这样呢?”意识到粉免可能有同伙的你决定使出杀手锏。
这次你想起了一道传说中的问题。
传说在月亮上住着很多只兔子,兔子有不同的颜色,比如粉兔,红兔,粉红兔,红粉兔…
月亮上有一个拥有 $n$ 个节点 $m$ 条边的无向的交通网络,每个节点上最多住着一只兔子。兔子们可以沿着交通网络里的路径前去拜访其他兔子,然后一起吃月饼。根据同类相斥、异类相吸的原理,兔子只想与其他颜色的兔子做朋友。而兔子是一种高冷的生物,喜欢独来独往,因此它们不希望自己在行程中遇到其他兔子。
传说中粉兔的情商和智商都特别特别高,所以总能规划出一种兔子的出行方案,使得朋友的对数最多。这一规划的过程俗称“找对”。
然而,你发现这传说根本就是在瞎扯,这么困难的问题,粉兔自然是不会做的,因此会做这个问题的只能是粉免。
于是你决定先自己算出最优解,然后再看看谁跟你求的解一致,就能知道谁是粉免啦。
形式化题意:
给一张图 $G = (V,E)$,其中每个点的颜色编号用 $c_i$ 表示,$c_i=0$ 则表示这个点没有颜色。找到最多的简单路径,使得:
- 没有两条路径相交,这里相交指有节点重合;
- 每条路径的两端都有颜色且两端颜色不相同。除了两端之外,路径不穿过任何有颜色的节点。
输入格式
第一行两个整数 $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\leqslant 6$ | $10$ |
$2$ | $n\leqslant 20$ | $15$ |
$3$ | $c_i\neq 0$ | $15$ |
$4$ | $c_i\leqslant 2$ | $20$ |
$5$ | 无 | $40$ |
对于所有数据,$1\leqslant n\leqslant 300$,$1\leqslant m\leqslant \binom{n}{2}$,$0\leqslant c_i\leqslant n$。
时间限制:$5\texttt{s}$
空间限制:$1\texttt{GB}$