Арсений любит собирать людей на вечеринки. Однако к нему помимо друзей приходят также друзья друзей, друзья друзей друзей и так далее. Таким образом даже Арсений может не знать всех пришедших к нему гостей. Он решил исправить это недоразумение при помощи следующего процесса:
На каждом шаге выбирается один человек A, который в свою очередь попарно знакомит всех своих знакомых. После этого все знакомые A попарно становятся друзьями. Это продолжается до тех пор, пока все гости не будут попарно знакомы.
Арсению очень хочется провести поменьше времени за этим процессом, поэтому он хочет его завершить за наименьшее число шагов. Помогите ему в этом.
В первой строке находятся два целых числа n и m (1 ≤ n ≤ 22; 
) — количество человек на вечеринке, включая Арсения, и количество пар знакомых людей.
В следующих m строках записаны по два целых числа u и v (1 ≤ u, v ≤ n; u ≠ v). Каждая такая пара обозначает, что люди с номерами u и v знакомы. Гарантируется, что каждая пара знакомств описывается не более одного раза, а также гарантируется, что данный граф знакомств связен.
В первую строку запишите наименьшее количество ходов, за которое можно попарно познакомить всех людей. Во второй строке для каждого ходы выведите номер гостя, который будет знакомить своих друзей на этом шаге. Если решений несколько, выведите любое.
5 6
1 2
1 3
2 3
2 5
3 4
4 5
2
2 3
4 4
1 2
1 3
1 4
3 4
1
1
В первом тестовом примере нет человека, который знал бы всех, поэтому для выполнения задачи требуется по меньшей мере два хода. После того, как второй перезнакомит всех своих друзей останутся незнакомыми только пары (4, 1) и (4, 2). Познакомить их может либо 3, либо 5.
Во втором тестовом примере гость номер 1 знает всех, поэтому за один ход может всех попарно познакомить.
