UOJ Logo Universal Online Judge

UOJ

#115. 【UER #2】谣言的传播

统计

由于电信技术的发展,谣言的传播变得十分迅速。

现在有 $n$ 个人,依次编号为 $1, \dots, n$。

每个人都有一个最好的朋友,第 $i$ 个人的最好的朋友为 $a_i$($a_i \neq i$)。

每个人都有一个真理捍卫者,第 $i$ 个人的真理捍卫者为 $b_i$($b_i \neq i$)。由于奇妙的原因,一个人只会是恰好一个人的真理捍卫者,即 $b_1, \dots, b_n$ 是一个 $1$ 到 $n$ 的排列。

对于第 $i$ 个人我们定义他的影响系数,考虑下面这个假想的谣言传播:

  1. 一开始,第 $i$ 个人从神奇的海螺那里听说了一则谣言。
  2. 每次,如果第 $j$ 个人首次听说了这则谣言,那么:
    • 如果 $j$ 是 $i$ 的真理捍卫者,即 $j = b_i$, 那么 $j$ 会不做任何事。
    • 否则, $j$ 会打电话把这则谣言告诉他最要好的朋友 $a_j$。
  3. 如果没有人首次听说了这则谣言那么传播过程结束。
  4. 最终,听说了谣言的人数为第 $i$ 个人的影响系数。

一万万年后,一位考古学家得到了 $a_1, \dots, a_n$,然而 $b_1, \dots, b_n$ 的取值在漫漫的历史长河中消失了。现在这位考古学家想求出所有人的影响系数之和的最小值与最大值,并给出相应的一组解。

输入格式

第一行一个正整数 $n$。保证 $n \geq 2$。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$。保证 $1 \leq a_i \leq n$ 且 $a_i \neq i$。

输出格式

第一行一个整数,表示影响系数之和的最小值。

接下来一行 $n$ 个整数 $b_1, \dots, b_n$ 表示一组满足影响系数之和最小的解。(如果有多组输出任意一组均可)

接下来一行一个整数,表示影响系数之和的最大值。

接下来一行 $n$ 个整数 $b_1, \dots, b_n$ 表示一组满足影响系数之和最大的解。(如果有多组输出任意一组均可)

样例一

input

5
4 1 5 3 4

output

11
4 1 5 3 2
18
2 5 4 1 3

样例二

见样例数据下载。

限制与约定

对于每个测试点,答对第一问可获得 50% 的分数,答对第二问可获得 50% 的分数。

请注意你输出的两组解必须合法否则该测试点会被直接判0分。(如果你输出的系数之和与解不相对应,只会导致该小问 $0$ 分,该测试点不会被直接判 $0$ 分)

测试点编号 $n$的规模
1$n \leq 8$
2$n \leq 50$
3
4
5$n \leq 2000$
6
7
8$n \leq 100000$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载