問題一覧 > 通常問題

No.1565 Union

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : 👑 PCTprobabilityPCTprobability / テスター : maguromaguro blackyukiblackyuki
2 ProblemId : 6342 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-21 20:41:50

問題文

$N$ 頂点 $0$ 辺のグラフが与えられます。

$M$ 本の辺の候補が与えられます。$i$ 本目の辺は、頂点 $a_i$ と頂点 $b_i$ をつなぐことができます。

頂点 $1$ と頂点 $N$ を連結にするためには、最低で何本の辺を使う必要があるか求めてください。

また、どのようにしても頂点 $1$ と頂点 $N$ を連結にすることができないならばそのことを報告してください。

入力

$N\ M$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_M\ b_M$

  • 入力は全て整数である。
  • $2 \le N,M \le 2 \times 10^5$
  • $1 \le a_i , b_i \le N$
  • $a_i \neq b_i$
  • $i \neq j$ ならば $(a_i,b_i) \neq (a_j,b_j)$
  • $i \neq j$ ならば $(a_i,b_i) \neq (b_j,a_j)$

出力

もし頂点 $1$ と頂点 $N$ を連結にできるのならば連結するために必要な辺の本数の最小値を出力してください。

どのようにしても頂点 $1$ と頂点 $N$ を連結にすることができないならば $-1$ を出力してください。

サンプル

サンプル1
入力
4 3
1 3
4 2
1 2
出力
2

辺 $2$ と辺 $3$ を使うことによって頂点 $1$ と頂点 $4$ を連結にすることができます。

また、$1$ 本以下の辺では頂点 $1$ と頂点 $4$ を連結にすることは不可能であることが証明できるため $2$ を出力します。

サンプル2
入力
5 3
1 3
5 4
4 2
出力
-1

どのようにしても頂点 $1$ と頂点 $N$ を連結にすることはできないので $-1$ を出力します。

サンプル3
入力
9 9
7 5
2 4
1 3
4 6
9 2
5 8
6 3
3 7
1 7
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。