The mafia in the city#1745
The mafia is already in the city. Rumor has it that the head of the mafia clan is planning to take control of the entire city, but first, he decided to focus on capturing the main communication lines.
There are base telephone stations in the city, some pairs of which are connected by bidirectional communication channels. For convenience, let's number the base stations from to . A communication channel is specified by a pair of numbers and — the numbers of the stations it connects.
We say that a communication channel is controlled by the mafia if either station or station (or both) has been captured.
The head of the mafia clan wants to control all communication channels while capturing as few base stations as possible. Your task is to help the telephone company's security service by creating a possible capture plan and determining the number of such plans.
The first line of the input file contains two integers: and (2 \leq n \leq 18, 0 \leq m). Each of the following lines describes one communication channel and contains two integers: and (1 \leq u, v \leq n, u \neq v) — the numbers of the base stations connected by this channel. Any pair of stations is connected by at most one channel.
In the first line of the output file, print two numbers: and — respectively, the minimum number of base stations that need to be captured to control all communication channels, and the number of ways to capture such a number of stations to control all communication channels.
In the second line of the output file, output numbers — the numbers of the base stations corresponding to one of the possible ways to capture.
Example 1