追記

• 8/21 15:29: テストケースの不備を修正、及び想定解の修正をしました。

AC報酬: $30$ ラテコイン

Story

🏝

matcharate君はGreenSea王国に来ました。この王国は主に個々の島からなる王国で、とても島から島への移動が複雑といった特徴を持っています。
そんな王国が、この不便さを改善できる人を募集していたのです。matcharate君はそれに参加しました。

前回、matcharate君は惑星 "VolNo" から魔法の杖をいただいていました。
Magenrate君曰く、この杖を使うことで島と島を繋ぐ橋を簡単に作り出すことができるそうです。

しかし、そんな簡便なものでもありません。
ですがmatcharate君は、この島と島をつなぐ橋をできる限り作って島の行き来を楽にしようと考えました。

...と、思いましたが、この王国にはmatcharate君の親友Apirateさんもいます。せっかくなので、橋を作り出して会いに行きましょう。

問題

GreenSea王国は $N$ 個の島と、島を互いに繋ぎあう $M$ 本の橋で構成されている、海面に面している国です。
島には順に $1,2,...,N$ と番号づけられており、$i\ (1\le i\le M)$ 本目の橋は島 $A_i$ と島 $B_i$ を互いに繋ぎあっています。

そんな中、matcharate君は島 $1$ にいます。matcharate君は以下の魔法を $0$ 回以上何回でも使うことができ、$1$ 回使うと以下の効果が得られます。

魔法

• 今いる島 $a$ として、島 $a$ と島 $a+K$ を互いに繋ぐ橋を新たに作る。ただし $a+K\gt N$ のときは魔法を使うことはできない。

この魔法を使い橋を使っていくつかの島を経由することで、Apirateさんがいる島 $N$ に向かおうと思っています。

matcharate君の目標を達成させるためには、少なくとも魔法を何回だけ使う必要がありますか？
ただしどのように魔法を使ってもたどり着けない場合は、その旨を報告してください。

入力

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

制約

• $2\le N\le 10^5$
• $0\le M\le \min(\frac{N(N-1)}{2},10^5)$
• $1\le K\le N-1$
• $1\le A_i\lt B_i\le N$
• $i\ \neq j\Rightarrow (A_i,B_i)\neq (A_j,B_j)$

出力

答えを出力せよ。ただしどのように魔法を使おうと目標を達成できないなら -1 を出力せよ。

入出力例

6 4 1
1 2
2 3
3 4
5 6

1

例えばmatcharate君は次のように移動し、魔法を使うことが最適です。

• 島 $1,2,3,4$ の順に移動し、島 $4$ で魔法を $1$ 回だけ使用する。その結果 $2$ つの島 $4,5$ 間を行き来できる橋が作られる。
• その橋を使い、島 $4,5,6$ の順に移動する

魔法を一回も使わずにたどり着く方法は存在しません。

3 0 1

2

島 $1$ で魔法を使い島 $2$ を結ぶ橋を作り、島 $2$ でもう一度魔法を使い、島 $3$ を結ぶ橋を作ると、島 $1,2,3$ を移動しながらたどり着くことができます。

6 2 4
2 3
4 5

-1

島 $1,5$ を結ぶ橋を作って島 $5$ に移動できます。 そこから島 $4$ に移動しますが、この時点で $4+4\gt 6$ となるため橋を作ることができません。
したがって目標を達成させることはできません。

13 8 1
1 3
3 5
4 6
7 8
7 9
8 9
10 11
12 13

4