幂一矩阵 ### 题目描述 天才少年的邻居 atm 最近学习了线性代数相关的理论，他对"矩阵"这个概念特别感兴趣。矩阵中有个概念叫做幂零矩阵。对于一个方阵 $M$ ，如果存在一个正整数 $k 满足 $M^k$ = 0 ，那么 $M\$ 就是一个幂零矩阵。 atm 不满足幂零矩阵，他自己设想了一个幂一矩阵：对于一个方阵 $M$ ，如果存在一个正整数 $k$ 满足 $M^k = I$ ，其中 $I$ 是单位矩阵，那么 $M$ 就是一个幂一矩阵。 atm 特别钟情于这样一种方阵：每行每列有且仅有一个 1 。经过 atm 不断实验，他发现这种矩阵都是幂一矩阵。 现在，他的问题是，给定一个满足以上条件的方阵，他想求最小的 $k$ 是多少。 ### 输入描述 第一行一个正整数 $n、 (n \leq 10^4)$ ，表示矩阵大小是 $n \times n$ 。 接下来 $n$ 行，每行两个正整数 $i, j$ 表示方阵的第 $i$ 行第 $j$ 列为 1。 其中，$1 \leq i, j \leq n$，行号，列号都从 1 开始。 ### 输出描述 输出一个正整数，即题目中所说最小的 $k$。 ### 输入输出样例 #### 示例 > 输入 ```txt 5 3 1 1 2 4 4 2 3 5 5 ``` > 输出 ```txt 3 ```