P1053 [NOIP 2005 Senior] Bonfire Party

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: $$(b_1, b_2, ..., b_{m-1}, b_m)$$ 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?

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 a single integer: the minimum total cost. If it is impossible to satisfy every student’s wish no matter how you rearrange, output $-1$.

- 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