Description

Jiajia has just entered high school. During military training, because Jiajia is hardworking and resilient, she quickly earned the instructor’s appreciation and became a “junior instructor” (xiao jiaoguan). On the last night of the training, Jiajia was ordered to organize a bonfire party. There are $n$ students, numbered from $1$ to $n$. Initially, the students sit in a circle in the order $1, 2, \cdots, n$. In reality, each person has two classmates they most wish to sit next to. How should Jiajia issue commands to rearrange the students into a new circle that satisfies everyone’s wishes? This is a big challenge for Jiajia.

Jiajia can issue commands, each of the following form:

Here, the value of $m$ is determined by Jiajia and can be different for each command. This command moves the positions of the $m$ students with numbers $b_1, b_2, \cdots, b_m$: $b_1$ moves to $b_2$’s position, $b_2$ moves to $b_3$’s position, …, and $b_m$ moves to $b_1$’s position. Executing each command incurs a cost. We assume that if a command moves $m$ people, then its cost is $m$. We need Jiajia to achieve everyone’s wishes with the minimum total cost. Can you help Jiajia?

Input Format

The first line contains an integer $n$, the total number of students.

The next $n$ lines each contain $2$ distinct positive integers, separated by a space. The $i$-th of these lines gives the numbers of the two classmates whom student $i$ most wishes to sit next to.

Output Format

Output a single integer: the minimum total cost. If it is impossible to satisfy every student’s wish no matter how you rearrange, output $-1$.

4
3 4
4 3
1 2
1 2

2

Hint

• For $30\%$ of the testdata, $n \le 1000$.
• For $100\%$ of the testdata, $3 \le n \le 50000$.

Source: NOIP 2005 Senior, Problem 3.

Translated by ChatGPT 5