問題一覧 > 通常問題

No.2565 First Errand

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 185
作問者 : 👑 loop0919 / テスター : deuteridayo 👑 AngrySadEight Kyo_s_s kusirakusira Magentor ragna マベマス(mavemas_413) けんぴん aki
お気に入りにしたユーザー ProblemId : 10168 / 自分の提出
問題文最終更新日: 2023-11-30 18:45:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回緑以下コンテスト (順位表) の他の問題:

Problem Statement

The country where Aoi lives has $N$ towns, numbered from $1$ to $N$.
There are also $M$ one-way roads connecting the towns. The $i$-th road $(1 \leq i \leq M)$ allows travel from town $u_i$ to town $v_i$.

At her older sister's request, Aoi will go on the following errand.

  • Start from her home in town $1$, visit both town $N-1$ and town $N$ at least $1$ time each, and return to her home in town $1$.

Find the length (the total number of roads traversed, counted with multiplicity) of the shortest route for the errand.
If the errand is impossible, print -1.

Constraints

  • $3 \leq N \leq 10^5$
  • $0 \leq M \leq \min(10^5, N(N-1))$
  • $1 \leq u_i, v_i \leq N$
  • $u_i \ne v_i$
  • $i \ne j \Longrightarrow (u_i, v_i) \ne (u_j, v_j)$
  • All input values are integers.

Input

The input is given in the following format.

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

Output

Print the answer. If the errand is impossible, print -1.

Sample

Sample 1
Input
4 6
1 2
2 4
2 3
3 1
3 4
4 3
Output
4

The country where Aoi lives is shown in the figure below.
One possible route for the errand is town $1$ $\rightarrow$ town $2$ $\rightarrow$ town $4$ $\rightarrow$ town $3$ $\rightarrow$ town $1$.
This is in fact a shortest route, so print $4$, the total number of roads traversed.

Sample 2
Input
3 3
1 2
3 1
2 1
Output
-1

The errand is impossible.

Sample 3
Input
7 12
1 2
1 4
1 5
2 5
3 1
3 2
4 1
4 6
5 1
5 6
6 7
7 3
Output
5

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