No.2565 First Errand
タグ : / 解いたユーザー数 185
作問者 : 👑
Kyo_s_s
kusirakusira
Magentor
ragna
けんぴん
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もしくは右上の雲マークをクリックしてアカウントを作成してください。