Problem C
Love Polygon
As we all know, TV soap operas with many characters can lead to seriously complicated love dramas. In one TV show, there are $N$ characters, numbered from $0$ to $N-1$. Character $i$ loves exactly one other character $a_i$ (which could actually be him- or herself). We say that two characters are in a relationship if and only if they love each other.
One particular type of complication is called a ‘love polygon’. We say that 3 or more characters are in a ‘love polygon’ if the first character loves the second, the second loves the third and so on, and also the last character loves the first.
Recent polling has shown that viewers have grown tired of this drama and would prefer something more romantic. Therefore, it was decided to shoot some characters with love arrows so that everyone is in a relationship. By shooting someone with a love arrow, you can change whom that character loves (to any character of your choice).
What is the least number of love arrows needed to get everyone into a relationship?
Input
The first line of the input contains the integer $N$, the number of characters involved. The next line contains $N$ numbers $a_i$, the characters loved by each character.
Output
Output one integer – the minimum number of love arrows needed to get everyone into a relationship. If this is not possible, output -1.
Constaints and Scoring
-
$2 \le N \le 100\, 000$.
-
$0 \leq a_i \leq N-1$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.
|
Group |
Score |
Limits |
|
1 |
21 |
$N \le 20$ |
|
2 |
25 |
Each character is loved by someone (possibly themselves) |
|
3 |
29 |
There are no relationships or ‘love polygons’ |
|
4 |
25 |
No additional contraints |
Examples
![\includegraphics[width=0.5\textwidth ]{polygonfig-num.pdf}](/problems/lovepolygon2/file/statement/en/img-0001.png)
The first example is illustrated in the figure above. The upper part shows the initial love situation, where an arrow pointing from $s$ to $t$ indicates that $s$ initially loves $t$, and the pink color highlights the three characters that needs to be shot with love arrows in the unique optimal solution. The lower part shows the situation afterwards.
In the second example (which satisfies the constraints of group 3), there are several optimal solutions. One of them is to shoot characters $0$, $1$ and $3$ with love arrows, and have them fall in love with characters $1$, $0$ and $2$, respectively.
In the third example, we have a love triangle, where no matter how many love arrows we shoot, someone will always be left out.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 3 4 0 5 1 6 3 3 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 2 3 3 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 2 0 |
-1 |
