Welcome Contest （京都・オープン） 2026/03/26 14:00 ~ 2026/03/26 18:00 4:00:00.000

I Daily Light

問題
制限時間: 2 sec メモリ制限: 1024 MB
Daily Light
Statement

Daylight 王国は、\(N\) 個 の都市と \(M\) 個の連絡線からなる巨大な王国です。各連絡線 \(i\) \((1 \leq i \leq M)\) は、都市 \(u_i\) から都市 \(v_i\) へ一方通行に連絡をすることが可能です。また、各都市には点滅可能な巨大な鉄塔が立っています。

Daylight 王国の王である Daylight 君は、最近国民の元気がないことを知り、彼らを勇気づけるためのプロジェクト「Daily Light」を実施することを決めました。

Daily Light プロジェクトでは、全ての都市の鉄塔が永遠に点灯することを目標とします。鉄塔の点滅ルールは、以下の通りです。

  • 各都市は、その日に自身が点灯したかどうかの情報を直接連絡を送信可能な都市に送信する
  • 各都市は、前日受信した情報の中に一つでも点灯連絡があった場合、鉄塔を点灯する（点灯連絡がない場合は消灯する）

Daylight 君は都市 \(1\) に住んでいるため、王様権限を1回使用することで各日に都市 \(1\) の鉄塔を点灯させることが可能です。

プロジェクトは、全ての都市の鉄塔が消灯した状態から始まります。 Daylight 君は、国民の信頼を損なわないようにするために王様権限の使用回数を出来るだけ少なくして、プロジェクトを完遂したいです。

この時、王様権限の使用回数が有限回に収まるかを判定し、収まるならばその最小値を求めて下さい。

Input

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

\(N~M\)
\(u_1~v_1\)
\(u_2~v_2\)
\(\vdots\)
\(u_M~v_M\)

入力は以下の制約をすべて満たします。

  • \(2 \leq N \leq 10^5\)
  • \(1 \leq M \leq \min(N(N-1), 2 \times 10^5\)
  • \(1 \leq u_i, v_i \leq N, u_i \neq v_i\)
  • 入力されるグラフには，自己ループが存在しない
  • 入力は全て整数

Output

王様権限の使用回数が有限回に収まるならばその最小値を出力してください。有限回に収まらない場合は \(-1\) を出力してください。

Examples

Input 1
4 4
1 2
2 3
3 4
4 1
Output 1
4
Input 2
7 8
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
Output 2
-1

Note

例\(1\) : 以下の手順で王様権限の使用回数を\(4\)回で Daily Light プロジェクトを達成可能である。

  • \(1\)日目：王様権限を使用する。この日、鉄塔が点灯している都市は都市\(1\)のみである。
  • \(2\)日目：王様権限を使用しない。都市\(2\)は都市\(1\)から昨日の点灯連絡を受信しているため鉄塔を点灯させる。鉄塔が点灯している都市は都市\(2\)のみである。
  • \(3\)日目：王様権限を使用する。都市\(3\)は都市\(2\)から昨日の点灯連絡を受信しているため鉄塔を点灯させる。鉄塔が点灯している都市は都市\(1, 3\)である。
  • \(4\)日目：王様権限を使用する。都市\(2, 4\)はそれぞれ都市\(1, 3\)から昨日の点灯連絡を受信しているため鉄塔を点灯させる。鉄塔が点灯している都市は都市\(1, 2, 4\)である。
  • \(5\)日目：王様権限を使用しない。都市\(1, 2, 3\)はそれぞれ都市\(4, 1, 2\)から昨日の点灯連絡を受信しているため鉄塔を点灯させる。鉄塔が点灯している都市は都市\(1, 2, 3\)である。
  • \(6\)日目：王様権限を使用する。都市\(2, 3, 4\)はそれぞれ都市\(1, 2, 3\)から昨日の点灯連絡を受信しているため鉄塔を点灯させる。鉄塔が点灯している都市は都市\(1, 2, 3, 4\)である。
  • \(7\)日目以降：王様権限を使用しなくても毎日各都市の鉄塔は点灯し続ける。

例\(2\) : 都市\(1\)の鉄塔を点灯させるには毎日王様権限を使用する必要がある。従って、永遠に点灯させるために王様権限の使用回数を有限回にすることは不可能である。

サンプル