atcoder#AGC004D. [AGC004D] Teleporter
[AGC004D] Teleporter
配点 : 点
問題文
高橋王国には 個の町があります。 町は から まで番号が振られています。 町 は首都です。
それぞれの町にはテレポーターが 台ずつ設置されています。 町 () のテレポーターの転送先は町 () です。 どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着けることが保証されます。
高橋王は正の整数 が好きです。 わがままな高橋王は、いくつかのテレポーターの転送先を変え、次の条件が成り立つようにしたいと思っています。
- どの町から出発しても、テレポーターをちょうど 回使うと、最終的に首都にいる。
条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを求めてください。
制約
- どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着ける。
入力
入力は以下の形式で標準入力から与えられる。
出力
条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを出力せよ。
3 1
2 3 1
2
テレポーターの転送先を と変えればよいです。
4 2
1 1 2 2
0
最初から条件が成り立っているので、テレポーターの転送先を変える必要はありません。
8 2
4 1 2 3 1 2 3 4
3
例えば、テレポーターの転送先を と変えればよいです。