C - 嘘つきな天使たち
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
天使の中に悪魔が紛れ込んだ。あなたは上司にこれを報告しなければならないが、上司は『最大でどれだけ悪魔が紛れ込んだか調査しろ』と命じてきた。
「一体、誰が悪魔なんですかね」
あなたが言うと、彼らは『あいつが悪魔だ』と指摘し合った。誰も同じ者を指ささずバラバラの者を指摘していた。
どうやら天使は必ず悪魔を、悪魔は必ず天使を指摘しているようだった。
最大で何人の悪魔がいるだろうか。その数を報告してほしい。
ただし、あなたや上司は天使でも悪魔でもなく、入力で与えられる『彼ら』には含まれない。また、『彼ら』はそれぞれ天使か悪魔のどちらかである。
入力
入力は以下の形式で標準入力から与えられる。
N A_{1} A_{2} : A_{N}
一つの整数 N と N 行の整数からなる。
i+1行目は番号iの者が番号A_{i}の者を指さしたことを示している。
ただし、2 \leq N \leq 10^5、1 \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