원숭이 춤

힌드 서커스의 단장은 새로운 공연인 원숭이 춤을 무대에 올리기로 했다. 원숭이 춤은 $N$마리의 원숭이가 동시에 추는 춤이다. 땅에는 $1$번부터 $N$번까지 번호가 매겨진 원이 $N$개 그려져 있고, 처음에 각 원숭이는 서로 다른 원 위에 한 마리씩 앉는다. 원들 사이에는 화살표가 $N$개 그려져 있는데, 각 원에서 나가는 화살표가 정확히 하나, 각 원으로 들어오는 화살표가 정확히 하나가 되도록 그려져 있다.

공연이 시작되면 단장이 호루라기를 불 때마다 모든 원숭이가 동시에, 자신이 있는 원에서 나가는 화살표를 따라 다른 원으로 뛴다. 이것이 춤의 한 단계이다. 모든 원숭이가 처음 앉았던 원으로 다시 돌아오면 춤이 끝난다. 이 춤은 몇 단계 동안 계속되는가?

입력은 여러 개의 테스트 케이스로 이루어질 수 있다. 각 테스트 케이스는 원의 개수 $N$ $(1 \le N \le 100)$이 적힌 줄로 시작하고, 이어지는 $N$개의 줄에는 각각 $1$ 이상 $N$ 이하의 정수 쌍이 주어진다. 정수 쌍 $I_1$, $I_2$는 원 $I_1$에서 원 $I_2$로 향하는 화살표가 있음을 뜻한다. $N$의 값으로 $0$이 주어지면 입력이 끝난다.

각 테스트 케이스마다 춤이 계속되는 단계 수를 한 줄에 하나씩 출력한다.