【codeforces】601A—— The Two Routes

柔情只为你懂 2022-09-25 07:27 2阅读 0赞

A. The Two Routes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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

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.

Examples

input

4 2
    1 3
    3 4

output

input

4 6
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4

output

-1

input

5 5
    4 2
    3 5
    4 5
    5 1
    1 2

output

Note

In the first sample, the train can take the route ![45307ea441d2996b4e3db04de8169f6600202297.png][] and the bus can take the route ![17348a86f2090cbcfe747091924a85e6176e16c0.png][]. 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.

水题，两个最短路径的事。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 405;
    const int M = 100000;
    int mp1[N][N],mp2[N][N],dis[N];
    bool vis[N];
    int n,m;
    void init() {
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			mp1[i][j]=i==j?0:INF;
    			mp2[i][j]=i==j?0:INF;
    		}
    	}
    }
    void dijkstra(int mp[N][N]) {
    	for(int i=1; i<=n; i++) {
    		dis[i]=INF;
    		vis[i]=false;
    	}
    	dis[1]=0;
    	for(int l=1; l<=n; l++) {
    		int tp=INF,k=-1;
    		for(int i=1; i<=n; i++) {
    			if(!vis[i]&&tp>dis[i]) {
    				tp=dis[i];
    				k=i;
    			}
    		}
    		if(tp==INF) {
    			break;
    		}
    		vis[k]=true;
    		for(int j=1; j<=n; j++) {
    			if(!vis[j]&&dis[j]>dis[k]+mp[k][j]) {
    				dis[j]=dis[k]+mp[k][j];
    			}
    		}
    	}
    }
    int main() {
    	while(scanf("%d%d",&n,&m)!=EOF) {
    		init();
    		int a,b;
    		for(int i=0; i<m; i++) {
    			scanf("%d%d",&a,&b);
    			mp1[a][b]=mp1[b][a]=1;
    		}
    		for(int i=1; i<=n; i++) {
    			for(int j=1; j<=n; j++) {
    				mp2[i][j]=mp2[j][i]=mp1[i][j]==INF?1:mp2[i][j];
    			}
    		}
    		int temp1,temp2;
    		dijkstra(mp1);
    		temp1=dis[n]==INF?-1:dis[n];
    		//printf("%d---\n",temp1);
    		dijkstra(mp2);
    		temp2=dis[n]==INF?-1:dis[n];
    		//printf("%d====\n",temp2);
    		if(temp1==-1||temp2==-1)
    			printf("-1\n");
    		else
    			printf("%d\n",max(temp1,temp2));
    	}
    	return 0;
    }

[题目地址：http://codeforces.com/problemset/problem/601/A][http_codeforces.com_problemset_problem_601_A]

[45307ea441d2996b4e3db04de8169f6600202297.png]: http://codeforces.com/predownloaded/45/30/45307ea441d2996b4e3db04de8169f6600202297.png
[17348a86f2090cbcfe747091924a85e6176e16c0.png]: /images/20220718/72ea997180cb43beb82b3c98d9c433c6.png
[http_codeforces.com_problemset_problem_601_A]: http://codeforces.com/problemset/problem/601/A