601A.md (2697B)
1 Source: https://codeforces.com/problemset/problem/601/A 2 3 A. The Two Routes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27 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. 28 29 Input 30 31 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. 32 33 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*). 34 35 You may assume that there is at most one railway connecting any two towns. 36 37 Output 38 39 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. 40 41 Examples 42 43 Input 44 45 ``` 46 4 2 47 1 3 48 3 4 49 ``` 50 51 Output 52 53 ``` 54 2 55 ``` 56 57 Input 58 59 ``` 60 4 6 61 1 2 62 1 3 63 1 4 64 2 3 65 2 4 66 3 4 67 ``` 68 69 Output 70 71 ``` 72 -1 73 ``` 74 75 Input 76 77 ``` 78 5 5 79 4 2 80 3 5 81 4 5 82 5 1 83 1 2 84 ``` 85 86 Output 87 88 ``` 89 3 90 ``` 91 92 Note 93 94 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. 95 96 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.