This was yet nobody knows, but many realize - the mafia is in town. Rumor has it that the plan is the head of a mafia clan seizure of control over the city, but at first he decided to limit the capture basic lines of the city. In the city there are \textbf{n} base exchanges, some couples are connected dvustronnimi communication channels. For convenience, we index the base stations are numbered from \textbf{1} to \textbf{n}, the communication channel in this case is given a pair of numbers (\textbf{u}, \textbf{v}) - numbers stations, which it connects. We say that a link (\textbf{u}, \textbf{v}) is \textit{controlled} by the mafia, if seized by a station \textbf{u}, a station \textbf{v} (or both). The head of a mafia clan wants to control all communication channels, while taking as little as possible base stations. Your task - to help the security service telephone company, making possible the capture plan and determining the number of such plans. \InputFile The first line contains two integers: \textbf{n} and \textbf{m} (\textbf{2} ≤ \textbf{n} ≤ 18, \textbf{0} ≤ \textbf{m}). Each of the following \textbf{m} lines describe a communication channel and contains two integers: \textbf{u} and \textbf{v} (\textbf{1} ≤ \textbf{u}, \textbf{v} ≤ \textbf{n}, \textbf{u} ≠ \textbf{v}) - number of base stations connected to this channel of communication. Any pair of stations connected by no more than one channel. \OutputFile The first line of the output file output two numbers: \textbf{k} and \textbf{c} - respectively, the minimum number of base stations, which must take in order to monitor all communication channels and methods of capture number so many stations, so as to control all communication channels. In the second row of the output file output \textbf{k} numbers - number of base stations corresponding to one of the methods of capture.