| VK Cup 2016 - Раунд 3 |
|---|
| Закончено |
В Беарляндии n городов, пронумерованных целыми числами от 1 до n. Города соединены двусторонними дорогами. Никакая дорога не соединяет город с самим собой, и никакая пара городов не соединена больше чем одной дорогой.
Однажды медвежонок Лимак оказался в городе a и захотел пойти в город b. Между ними не было прямой дороги, поэтому он решил прогуляться и посетить каждый город ровно один раз. Формально:
- Не существует дороги между городами a и b.
- Существует путь, состоящий из n различных городов v1, v2, ..., vn, такой что v1 = a, vn = b, а города vi и vi + 1 соединены дорогой при
.
На другой день ситуация повторилась. Лимак находился в городе c и хотел отправиться в город d, но дороги между ними не было, поэтому он решил прогуляться по длинному пути из n различных городов u1, u2, ..., un, такому что u1 = c, un = d, и между ui и ui + 1 есть дорога для .
Лимак полагает, что в Беарляндии не более k дорог, и просит вас проверить, может ли так быть, что он всё помнит правильно. По данным n, k и четырём различным индексам городов a, b, c и d, восстановите два пути (v1, ..., vn) и (u1, ..., un), которые удовлетворят всем условиям, или определите, что это невозможно.
В первой строке входных данных записаны два числа n и k (4 ≤ n ≤ 1000, n - 1 ≤ k ≤ 2n - 2) — количество городов и максимально допустимое количество дорог соответственно.
Во второй строке записаны четыре различных числа a, b, c и d (1 ≤ a, b, c, d ≤ n).
Если выполнить все условия невозможно, то выведите -1 в единственной строке выходных данных. В противном случае выведите две строки с описанием путей.
Первая из них должна содержать n различных индексов городов v1, v2, ..., vn, и при этом должно выполняться v1 = a и vn = b. Вторая строка аналогично содержит n различных индексов u1, u2, ..., un, описывающих второй путь, то есть должно выполняться u1 = c и un = d.
Эти два пути определяют не более чем 2n - 2 дорог: (v1, v2), (v2, v3), ..., (vn - 1, vn), (u1, u2), (u2, u3), ..., (un - 1, un). Ваш ответ будет считаться неправильным, если различных дорог будет больше k или будет нарушено какое-то другое условие.
Обратите внимание, что (x, y) и (y, x) обозначают одну и ту же дорогу.
7 11
2 4 7 3
2 7 1 3 6 5 4
7 1 5 4 6 2 3
1000 999
10 20 30 40
-1
В первом примере должно быть 7 городов и не более 11 дорог. В представленном решении содержится 10 дорог, как на картинке. Также показаны простые пути длины n между 2 и 4 и между 7 и 3.
