3989. Florr

【题目背景】

玩 Florr 玩的。

【题目描述】

小 Van 喜欢玩 Florr。

游戏中的人物有 $m$ 个装备栏，分别编号为 $1,2,…,m$。小 Van 有 $n$ 件可用的装备，分别编号为 $1,2,…,n$。编号为 $i$ 的装备提供 $c_i (1\le c_i\le n)$ 点属性。

为了让玩家能够更灵活地搭配装备以应付不同的情况，游戏中的每个装备栏都可以装备两件装备，但同一时刻只能使用其中的一件。并且，同一件装备可以同时装备在多个装备栏中，但同一时刻只有其中的一个装备栏能使用这件装备。玩家可以随时切换装备，即选择一个装备栏，然后交换这个装备栏中正在使用和未使用的装备，但如果交换之前未使用的装备在其他装备栏中正在被使用，则不能交换。

小 Van 发现，如果他的第 $i$ 个装备栏中正在使用的装备提供了 $X_i$ 点属性，则他的战斗力为

$$\sum_{1\le i\le m}{X_i\cdot n^i}$$

小 Van 现在的第 $i$ 个装备栏中的装备是 $a_i$ 和 $b_i$，其中 $a_i$ 正在使用，$b_i$ 未使用。小 Van 想知道，如果他能够进行至多 $k$ 次装备的切换，他能够达到多强的战斗力？找到一种达到最大战斗力的切换装备的方案。

【输入格式】

第一行三个整数 $n, m, k (2\le n\le 10^5, 1\le m\le n, 0\le k\le n)$，分别表示小 Van 拥有的装备数量、装备栏的数量以及能够进行装备切换的次数。

第二行 $n$ 个整数 $c_1,c_2,…,c_n (1\le c_i\le n)$，表示每件装备提供的属性。

接下来的 $m$ 行中，第 $i$ 行两个整数 $a_i, b_i (1\le a_i,b_i\le n, a_i \neq b_i$)，表示小 Van 的 $i$ 个装备栏中的装备。保证所有 $a_i$ 互不相同。

【输出格式】

在第一行输出交换装备的次数 $k′ (0\le k′\le k)$。

接下来 $k′$ 行，每行一个整数 $s_i (1\le s_i\le m)$，表示第 $i$ 次切换的装备栏编号。在每次切换后都要满足每个装备栏正在使用的装备互不相同。

你的方案需要满足战斗力是所有可行方案中最大的。如果有多个方案，输出任意一个均可。

【样例输入1】

2 2 2
1 2
1 2
2 1

【样例输出1】

0

【样例输入2】

2 1 1
1 2
1 2

【样例输出2】

1
1

【样例输入3】

3 2 1
1 2 3
1 2
2 3

【样例输出3】

1
2

【样例输入4】

3 2 2
1 2 3
1 2
2 3

【样例输出4】

2
2
1

【样例输入5】

15 14 5
14 3 5 1 14 2 7 8 10 15 4 5 1 11 10
13 2
7 13
4 13
10 2
15 10
6 2
5 7
3 10
1 15
8 1
12 7
11 7
14 11
9 15

【样例输出5】

3
1
2
12

【样例说明】

在第一组样例中，切换任意一个装备栏都会导致同一个装备同时在两个装备栏中使用，因此小 Van 无法进行任何切换。 

在第二组样例中，初始时的战斗力为 $1\times 2=2$，切换之后的战斗力为 $2 \times 2 = 4 $，因此进行一次切换最优。

在第三组样例中，小 Van 只能切换第二个装备栏，切换后的战斗力为 $1\times 3+3\times 3^2 =30$。 

在第四组样例中，相比第三组样例，小 Van 可以多进行一次切换，因此小 Van 可以在切换第二个装备栏后再切换第一个装备栏，最终的战斗力为 $2 \times 3 + 3 \times 3^2 = 33$。

【数据规模与约定】

对于 $100\%$ 的数据：$1 \le n \le 10^5,1\le m\le n,0\le k\le n$。

·$Subtask1(20pts): n\le 20$。

·$Subtask2(40pts): n\le 3000$。

·$Subtask3(10pts): k=n$。

·$Subtask4(30pts): 无特殊限制$。

致敬传奇 Florr 高手小 Van。

【来源】

在此键入。