codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/7c0aa60a06309ef607b7159fd7f3687ea0d943ce.png) and the bus can take the route ![](https://espresso.codeforces.com/a26c2f3e93c9d9be6c21cb5d2bd6ac1f99f4ff55.png). 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.