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 . 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 . 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 