C - 嘘つきな天使たち 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100

問題文

天使の中に悪魔が紛れ込んだ。あなたは上司にこれを報告しなければならないが、上司は『最大でどれだけ悪魔が紛れ込んだか調査しろ』と命じてきた。

「一体、誰が悪魔なんですかね」

あなたが言うと、彼らは『あいつが悪魔だ』と指摘し合った。誰も同じ者を指ささずバラバラの者を指摘していた。

どうやら天使は必ず悪魔を、悪魔は必ず天使を指摘しているようだった。

最大で何人の悪魔がいるだろうか。その数を報告してほしい。

ただし、あなたや上司は天使でも悪魔でもなく、入力で与えられる『彼ら』には含まれない。また、『彼ら』はそれぞれ天使か悪魔のどちらかである。

入力

入力は以下の形式で標準入力から与えられる。

N
A_{1}
A_{2}
:
A_{N}

一つの整数 NN 行の整数からなる。

i+1行目は番号iの者が番号A_{i}の者を指さしたことを示している。

ただし、2 \leq N \leq 10^51 \leq A_{i} \leq N であり、 相異なる任意の i, j について A_i≠A_j である。

出力

考えられる悪魔の数として最大のものを一行に出力せよ。

どのように天使と悪魔を決めても矛盾が生じるなら-1を出力せよ。


入力例 1

4
2
3
4
1

出力例 1

2

入力例 2

3
2
3
1

出力例 2

-1