Idempotent functions

题意翻译

给定一个定义域为 $[1,n]$ 的函数 $f(x)$ ，并告诉你 $f(1),f(2)\dots f(n-1),f(n)$，定义 $f^{(k)}(x)=f(f^{(k-1)}(x))$ 。求一个最小的 $k$ 使得 $\forall x \in [1,n]$ ，都有 $f^{(k)}(f^{(k)}(x))=f^{(k)}(x)$ 。 第一行输入一个正整数 $n(1\le n\le 200)$ ，第二行 $n$ 个正整数表示 $f(i)(1\le f(i)\le n)$ 。

题目描述

Some time ago Leonid have known about idempotent functions. Idempotent function defined on a set $ {1,2,...,n} $ is such function , that for any  the formula $ g(g(x))=g(x) $ holds. Let's denote as $ f^{(k)}(x) $ the function $ f $ applied $ k $ times to the value $ x $ . More formally, $ f^{(1)}(x)=f(x) $ , $ f^{(k)}(x)=f(f^{(k-1)}(x)) $ for each $ k>1 $ . You are given some function . Your task is to find minimum positive integer $ k $ such that function $ f^{(k)}(x) $ is idempotent.

输入输出格式

输入格式

In the first line of the input there is a single integer $ n $ ( $ 1<=n<=200 $ ) — the size of function $ f $ domain. In the second line follow $ f(1),f(2),...,f(n) $ ( $ 1<=f(i)<=n $ for each $ 1<=i<=n $ ), the values of a function.

输出格式

Output minimum $ k $ such that function $ f^{(k)}(x) $ is idempotent.

输入输出样例

输入样例 #1

4
1 2 2 4

输出样例 #1

1

输入样例 #2

3
2 3 3

输出样例 #2

2

输入样例 #3

3
2 3 1

输出样例 #3

3

说明

In the first sample test function $ f(x)=f^{(1)}(x) $ is already idempotent since $ f(f(1))=f(1)=1 $ , $ f(f(2))=f(2)=2 $ , $ f(f(3))=f(3)=2 $ , $ f(f(4))=f(4)=4 $ . In the second sample test: - function $ f(x)=f^{(1)}(x) $ isn't idempotent because $ f(f(1))=3 $ but $ f(1)=2 $ ; - function $ f(x)=f^{(2)}(x) $ is idempotent since for any $ x $ it is true that $ f^{(2)}(x)=3 $ , so it is also true that $ f^{(2)}(f^{(2)}(x))=3 $ . In the third sample test: - function $ f(x)=f^{(1)}(x) $ isn't idempotent because $ f(f(1))=3 $ but $ f(1)=2 $ ; - function $ f(f(x))=f^{(2)}(x) $ isn't idempotent because $ f^{(2)}(f^{(2)}(1))=2 $ but $ f^{(2)}(1)=3 $ ; - function $ f(f(f(x)))=f^{(3)}(x) $ is idempotent since it is identity function: $ f^{(3)}(x)=x $ for any  meaning that the formula $ f^{(3)}(f^{(3)}(x))=f^{(3)}(x) $ also holds.