Farmer John's N cows (1 <= N <= 100), conveniently numbered 1..N, are standing in a row. Their ordering is described by an array A, where A(i) is the number of the cow in position i. Farmer John wants to rearrange them into a different ordering for a group photo, described by an array B, where B(i) is the number of the cow that should end up in position i.

To re-arrange themselves from the "A" ordering to the "B" ordering, the cows perform a number of "cyclic" shifts. Each cyclic shift begins with a cow moving to her proper location in the "B" ordering, displacing another cow, who then moves to her proper location, displacing another cow, and so on, until eventually a cow ends up in the position initially occupied by the first cow on the cycle. The cows keep performing cyclic shifts until every cow eventually ends up in her proper location. Each cow participates in exactly one cyclic shift, unless she occupies the same position in the "A" and "B" orderings.

Please compute the number of different cyclic shifts, as well as the length of the longest cyclic shift, as the cows rearrange themselves.

Line 1: The integer N.

Lines 2..1+N: Line i+1 contains the integer A(i).

Lines 2+N..1+2N: Line 1+N+i contains the integer B(i).

Two space-separated integers, the first giving the number of cyclic shifts and the second giving the number of cows involved in the longest such shift. If there are no cyclic shifts, output -1 for the second number.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > March > Bronze