← 返回题目列表

Codeforces · 542/C

C. 幂等函数

中文机器翻译题面 查看原题

不久前,Leonid 已经知道幂等函数了。在集合 {1, 2, ..., n} 上定义的幂等函数是这样的函数 $$g:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$$,对于任何 $$x \in \{1, 2, \ldots, n\}$$,公式 g(g(x)) = g(x) 成立。

我们将函数 f 对值 x 应用 k 次表示为 f(k)(x)。更正式地说,对于每个 k > 1,f(1)(x) = f(x)、f(k)(x) = f(f(k - 1)(x))。

给你一些函数 $$f: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$$。您的任务是找到最小正整数 k,使得函数 f(k)(x) 具有幂等性。

输入

在输入的第一行中有一个整数 n (1 ≤ n ≤ 200) — 函数 f 域的大小。

在第二行中,f(1), f(2), ..., f(n) (对于每个 1 ≤ i ≤ n,1 ≤ f(i) ≤ n),函数的值。

输出

输出最小 k 使得函数 f(k)(x) 是幂等的。

示例

输入 #1

4
1 2 2 4

输出 #1

1

输入 #2

3
2 3 3

输出 #2

2

输入 #3

3
2 3 1

输出 #3

3

注意

在第一个示例测试函数中,f(x) = f(1)(x) 已经是幂等的,因为 f(f(1)) = f(1) = 1、f(f(2)) = f(2) = 2、f(f(3)) = f(3) = 2、f(f(4)) = f(4) = 4。

在第二个样本测试中:

- 函数 f(x) = f(1)(x) 不是幂等的,因为 f(f(1)) = 3 但 f(1) = 2;
- 函数 f(x) = f(2)(x) 是幂等的,因为对于任何 x,f(2)(x) = 3 成立,因此 f(2)(f(2)(x)) = 3 也成立。

在第三个样本测试中:

- 函数 f(x) = f(1)(x) 不是幂等的,因为 f(f(1)) = 3 但 f(1) = 2;
- 函数 f(f(x)) = f(2)(x) 不是幂等的,因为 f(2)(f(2)(1)) = 2 但 f(2)(1) = 3;
- 函数 f(f(f(x))) = f(3)(x) 是幂等的,因为它是恒等函数: f(3)(x) = x 对于任何 $$x \in \{1, 2, 3\}$$ 意味着公式 f(3)(f(3)(x)) = f(3)(x) 也成立。