402657: GYM100834 F Polycarp and Satellites

Polycarp likes build space satellites. He learned ideas of projects from Provectus Inc. He knows, that one big satellite is very expensive and is requred to launch a rocket, but N small satellites is cheaper and you can launch satellites, just using special airplane. In that case Polycarp should organize a transmission of data among satellites. He can make two way channel of data transmission between any two different satellites. But a channel requires to install expensive devices on satellites and therefore Polycarp wants to make at most 4·N channels to his satellites. Between any pair of satellites can not be more than 1 channel.

Polycarp wants to know which pairs of satellites he should connect with channels, such that if any K channels are destroyed, then we can find path from any satellite to any another one maybe via other satellites.

The input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists.

The first line contains M — the number of channels. M lines follow, each contains a_i and b_i — numbers of satellites are connected by i channel, M ≤ 4·N.

5 2

8
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

6 2

9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6