UOJ Logo Universal Online Judge

UOJ

#785. 新年的找对

附件下载 统计

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

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

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

月亮上有一个拥有 $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\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}$