레이팅 미적용농부 존의 소 N마리(1 <= N <= 100)는 편의상 1..N으로 번호가 붙어 있으며, 한 줄로 서 있다. 이들의 순서는 배열 A로 표현되는데, A(i)는 위치 i에 있는 소의 번호이다. 농부 존은 단체 사진을 위해 이들을 다른 순서로 재배열하려고 하며, 그 순서는 배열 B로 표현되고, B(i)는 위치 i에 최종적으로 있어야 할 소의 번호이다.
"A" 순서에서 "B" 순서로 재배열하기 위해 소들은 여러 번의 "순환" 이동을 수행한다. 각 순환 이동은 한 소가 "B" 순서에서의 자기 자리로 이동하며 다른 소를 밀어내는 것으로 시작하고, 밀려난 소가 다시 자기 자리로 이동하며 또 다른 소를 밀어내는 식으로 이어지다가, 결국 어떤 소가 순환의 첫 번째 소가 처음에 있던 위치에 도착하면서 끝난다. 소들은 모든 소가 자기 자리에 도착할 때까지 순환 이동을 계속 수행한다. 각 소는 "A" 순서와 "B" 순서에서 같은 위치를 차지하는 경우가 아니라면 정확히 하나의 순환 이동에 참여한다.
소들이 재배열하는 동안 서로 다른 순환 이동의 개수와 가장 긴 순환 이동의 길이를 계산하라.
첫째 줄: 정수 N이 주어진다.
둘째 줄부터 1+N째 줄까지: i+1째 줄에는 정수 A(i)가 주어진다.
2+N째 줄부터 1+2N째 줄까지: 1+N+i째 줄에는 정수 B(i)가 주어진다.
공백으로 구분된 두 정수를 출력한다. 첫 번째는 순환 이동의 개수이고, 두 번째는 가장 긴 순환 이동에 참여하는 소의 수이다. 순환 이동이 없으면 두 번째 수로 -1을 출력한다.
reorder.in · 출력을 쓸 파일 reorder.out5
5
1
4
2
3
2
5
3
1
42 3Output details: There are two cyclic shifts: one involving cows 5, 1, and 2, and the other involving cows 3 and 4.