2014
02-24

# A poor officer

There are n soldiers numbered from 1 to n in a troop. They stand in a line according to their numbers, which means the soldier numbered i stands at the ith position. But the officer of this troop is unsatisfied with the arrangement, he decides to rearrange it. After a careful consideration, the officer develops such rearrangement as follows: He thinks up a permutation of 1 to n, and then commands the aith soldier to stand in the ith position in the new arrangement. However, the new sequence still cannot meet the officer’s need. So they have to apply the arrangement repeatedly according to the method the officer thinks up.

For example, there are 5 soldiers in the troop; the permutation in the officer’s mind is 2 1 4 5 3. After the first rearrangement, the troop sequence is 2 1 4 5 3. After the second rearrangement, the sequence becomes 1 2 5 3 4.

Unluckily, after a long time of rearrangements, the officer and the soldiers are very tired but the strict officer is still unsatisfied. The poor officer asks the soldiers, “Who can tell me the least times of rearrangements needed to reach the arrangement I like.” As the smartest soldier you decide to answer the officer’s question.
Here is an example: if there are 5 soldiers in the troop, the permutation in the officer’s mind is 2 1 4 5 3. He wants the troop to be 2 1 3 4 5. The rearrangements are as follows:

The input contains several cases. Each case is described as follows:

1st line: n, the number of soldiers (0 < n ≤ 10,000).

2nd line: a1 a2 … an, the permutation that the troop applies each time.

3rd line: b1 b2 … bn, the target arrangement the officer is satisfied with.

The last case is followed by a line containing one zero.

The input contains several cases. Each case is described as follows:

1st line: n, the number of soldiers (0 < n ≤ 10,000).

2nd line: a1 a2 … an, the permutation that the troop applies each time.

3rd line: b1 b2 … bn, the target arrangement the officer is satisfied with.

The last case is followed by a line containing one zero.

5
2 1 4 5 3
2 1 3 4 5
0

3

1. #include <cstdio>

int main() {