Minimum Total Cost of Cyclic Shifts for Desired Circle Arrangement

During military training, JiaJia was quickly promoted to a 'small instructor'. On the final evening, JiaJia was ordered to organize a bonfire party. There are n students numbered from 1 to n sitting in a circle in the order 1,2,…,n. In fact, every student has two specific other students that they most wish to sit next to. A final circle arrangement is considered valid if for every student i (with 1 ≤ i ≤ n), the two students sitting adjacent to i (neighbors in the circle) are exactly the two students chosen by i (order does not matter).

JiaJia can issue commands to reorder the circle. Each command is of the form \[ (b_1, b_2, \dots, b_m) \] which means that the positions of the students with numbers b₁, b₂, …, b_m will be cyclically shifted: b₁ moves to the position of b₂, b₂ moves to the position of b₃, …, and b_m moves to the position of b₁. The cost of a command that moves m students is m.

The task is to determine the minimum total cost necessary to transform the initial circle arrangement (1,2,…,n) into a valid circle arrangement that satisfies every student’s desired neighbors. It is guaranteed that a valid arrangement exists. Note that a valid arrangement is unique up to a reversal of order; you may choose either one as the target.

Hint: Once the target arrangement is determined, computing the minimum cost to transform the identity permutation into the target permutation can be done by decomposing the permutation into disjoint cycles. For each cycle with length L > 1, the cost is L (since a cyclic shift command on L elements costs L), while cycles of length 1 require no moves.

Formally, if the permutation mapping from the initial arrangement to the target arrangement is decomposed as disjoint cycles, then the answer is the sum of the lengths of cycles with length at least 2.

inputFormat

The input begins with an integer n (the number of students). The next n lines each contain two integers. The i-th of these lines (1 ≤ i ≤ n) contains two distinct integers which denote the two students that student i wishes to sit next to.

outputFormat

Output a single integer: the minimum total cost required to achieve a valid circle arrangement from the initial arrangement.

sample

4
2 4
1 3
2 4
1 3

0