{"raw_statement":[{"iden":"statement","content":"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.\n\nPolycarp 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.\n\nThe input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists.\n\nThe first line contains M — the number of channels. M lines follow, each contains ai and bi — numbers of satellites are connected by i channel, M ≤ 4·N.\n\n"},{"iden":"input","content":"The input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists."},{"iden":"output","content":"The first line contains M — the number of channels. M lines follow, each contains ai and bi — numbers of satellites are connected by i channel, M ≤ 4·N."},{"iden":"examples","content":"Input5 2Output81 31 41 52 32 42 53 43 5Input6 2Output91 41 51 62 42 52 63 43 53 6"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of satellites, $ K \\in \\mathbb{Z} $ be the maximum number of channels that can be destroyed.  \nLet $ G = (V, E) $ be an undirected graph where $ V = \\{1, 2, \\dots, N\\} $ represents satellites and $ E \\subseteq \\binom{V}{2} $ represents communication channels.\n\n**Constraints**  \n1. $ 3 \\leq N \\leq 20 $  \n2. $ 1 \\leq K \\leq 5 $  \n3. $ |E| \\leq 4N $  \n4. $ |E| \\geq \\binom{N}{2} $ is not required; $ E $ may be sparse.  \n5. $ G $ must remain connected after the removal of any $ K $ edges (i.e., $ G $ is $ (K+1) $-edge-connected).\n\n**Objective**  \nFind a set $ E $ of edges such that $ G = (V, E) $ is $ (K+1) $-edge-connected and $ |E| \\leq 4N $.  \nOutput $ |E| $, followed by the $ |E| $ pairs $ (a_i, b_i) \\in E $.","simple_statement":"Connect N satellites with at most 4·N channels so that even if any K channels fail, all satellites remain connected. Output the list of channel pairs.","has_page_source":false}