CF542C Idempotent functions

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.

N/A

N/A

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.