CF601A.The Two Routes

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

In Absurdistan, there are $n$ towns (numbered $1$ through $n$ ) and $m$ bidirectional railways. There is also an absurdly simple road network — for each pair of different towns $x$ and $y$ , there is a bidirectional road between towns $x$ and $y$ if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town $1$ at the same time. They both have the same destination, town $n$ , and don't make any stops on the way (but they can wait in town $n$ ). The train can move only along railways and the bus can move only along roads.

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town $n$ ) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town $n$ (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town $n$ at the same moment of time, but are allowed to do so.

输入格式

The first line of the input contains two integers $n$ and $m$ ( $2<=n<=400$ , $0<=m<=n(n-1)/2$ ) — the number of towns and the number of railways respectively.

Each of the next $m$ lines contains two integers $u$ and $v$ , denoting a railway between towns $u$ and $v$ ( $1<=u,v<=n$ , $u≠v$ ).

You may assume that there is at most one railway connecting any two towns.

输出格式

Output one integer — the smallest possible time of the later vehicle's arrival in town $n$ . If it's impossible for at least one of the vehicles to reach town $n$ , output $-1$ .

输入输出样例

输入#1
```
4 2
1 3
3 4
```
输出#1
```
2
```
输入#2
```
4 6
1 2
1 3
1 4
2 3
2 4
3 4
```
输出#2
```
-1
```
输入#3
```
5 5
4 2
3 5
4 5
5 1
1 2
```
输出#3
```
3
```

说明/提示

In the first sample, the train can take the route and the bus can take the route . Note that they can arrive at town $4$ at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town $4$ .

首页