AT_abc397_g [ABC397G] Maximize Distance

$ N $ 頂点 $ M $ 辺の有向グラフが与えられます。頂点には $ 1,2,\dots,N $ の番号がついており、辺 $ j $ ( $ j=1,2,\dots,M $ ) は頂点 $ u_j $ から頂点 $ v_j $ に向かいます。ここで、頂点 $ 1 $ から頂点 $ N $ に到達可能であることが保証されます。 はじめ、すべての辺の重みは $ 0 $ です。 $ M $ 本の辺からちょうど $ K $ 本の辺を選んで重みを $ 1 $ に変更するとき、変更後のグラフにおける頂点 $ 1 $ から頂点 $ N $ への最短距離としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

答えを出力せよ。

### Sample Explanation 1 辺 $ 1,3 $ を選べば、頂点 $ 1 $ から頂点 $ 3 $ への最短距離が $ 1 $ になります。最短距離を $ 2 $ 以上にする選び方は存在しないので、答えは $ 1 $ です。 ### Sample Explanation 2 辺 $ 1,2,4 $ を選べば、頂点 $ 1 $ から頂点 $ 4 $ への最短距離が $ 2 $ になります。最短距離を $ 3 $ 以上にする選び方は存在しないので、答えは $ 2 $ です。 ### Sample Explanation 3 多重辺が存在しうることに注意してください。 ### Constraints - $ 2 \leq N \leq 30 $ - $ 1 \leq K \leq M \leq 100 $ - $ 1 \leq u_j,v_j \leq N $ - $ u_j \neq v_j $ - 与えられるグラフにおいて、頂点 $ 1 $ から頂点 $ N $ へ到達可能である - 入力はすべて整数