codeforces-scrape

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

643B.md (3174B)


      1 Source: https://codeforces.com/problemset/problem/643/B
      2 
      3 B. Bear and Two Paths
      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 Bearland has *n* cities, numbered 1 through *n*. Cities are connected via bidirectional roads. Each road connects two distinct cities. No two roads connect the same pair of cities.
     22 
     23 Bear Limak was once in a city *a* and he wanted to go to a city *b*. There was no direct connection so he decided to take a long walk, visiting each city exactly once. Formally:
     24 
     25 * There is no road between *a* and *b*.
     26 * There exists a sequence (path) of *n* distinct cities *v*1, *v*2, ..., *v**n* that *v*1 = *a*, *v**n* = *b* and there is a road between *v**i* and *v**i* + 1 for ![](https://espresso.codeforces.com/23e5d4ea4f6228395f4a124f9060fbe08e8efbfc.png).
     27 
     28 On the other day, the similar thing happened. Limak wanted to travel between a city *c* and a city *d*. There is no road between them but there exists a sequence of *n* distinct cities *u*1, *u*2, ..., *u**n* that *u*1 = *c*, *u**n* = *d* and there is a road between *u**i* and *u**i* + 1 for ![](https://espresso.codeforces.com/23e5d4ea4f6228395f4a124f9060fbe08e8efbfc.png).
     29 
     30 Also, Limak thinks that there are at most *k* roads in Bearland. He wonders whether he remembers everything correctly.
     31 
     32 Given *n*, *k* and four distinct cities *a*, *b*, *c*, *d*, can you find possible paths (*v*1, ..., *v**n*) and (*u*1, ..., *u**n*) to satisfy all the given conditions? Find any solution or print -1 if it's impossible.
     33 
     34 Input
     35 
     36 The first line of the input contains two integers *n* and *k* (4 ≤ *n* ≤ 1000, *n* - 1 ≤ *k* ≤ 2*n* - 2) — the number of cities and the maximum allowed number of roads, respectively.
     37 
     38 The second line contains four distinct integers *a*, *b*, *c* and *d* (1 ≤ *a*, *b*, *c*, *d* ≤ *n*).
     39 
     40 Output
     41 
     42 Print -1 if it's impossible to satisfy all the given conditions. Otherwise, print two lines with paths descriptions. The first of these two lines should contain *n* distinct integers *v*1, *v*2, ..., *v**n* where *v*1 = *a* and *v**n* = *b*. The second line should contain *n* distinct integers *u*1, *u*2, ..., *u**n* where *u*1 = *c* and *u**n* = *d*.
     43 
     44 Two paths generate at most 2*n* - 2 roads: (*v*1, *v*2), (*v*2, *v*3), ..., (*v**n* - 1, *v**n*), (*u*1, *u*2), (*u*2, *u*3), ..., (*u**n* - 1, *u**n*). Your answer will be considered wrong if contains more than *k* distinct roads or any other condition breaks. Note that (*x*, *y*) and (*y*, *x*) are the same road.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 7 11  
     52 2 4 7 3
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2 7 1 3 6 5 4  
     59 7 1 5 4 6 2 3
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 1000 999  
     66 10 20 30 40
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 -1
     73 ```
     74 
     75 Note
     76 
     77 In the first sample test, there should be 7 cities and at most 11 roads. The provided sample solution generates 10 roads, as in the drawing. You can also see a simple path of length *n* between 2 and 4, and a path between 7 and 3.
     78 
     79  ![](https://espresso.codeforces.com/58dec3e8514751ba57473ff99eae98f6a4c57658.png)