The Conquest of the Kingdom#3056
In a magical kingdom, there are cities, each pair connected by a road. These roads were built long ago by the forces of Light and Darkness: roads built by the Light forces are paved with white stones, and those by the Dark forces are paved with black stones. Because of magical charms, no good creature can travel on a road paved with black stones, and no evil creature can travel on a white road.
Long ago, the people decided to choose their rulers and expelled the supreme mages from the kingdom. Recently, however, the supreme mages of the Light and Dark forces reached an agreement to reclaim the kingdom. To achieve this, they plan to send mages to certain cities so that those cities and their neighboring cities will come under control.
Precisely, if a Light mage is sent to a city, that mage will take control of the city and all cities directly connected to it by white roads. Similarly, a Dark mage, besides the city to which he is sent, will control all cities directly connected to it by black roads. To capture the kingdom, it is necessary to take control of all cities.
However, two difficulties have arisen in the plan. First, a mage will only agree to participate if all mages sent to the kingdom represent the same force as he does. That is, either all the mages must be Light, or all must be Dark. Secondly, the total number of mages sent to the kingdom must not exceed .
The supreme mages hope that is large enough, i.e., 2^K \geq N.
Determine whether it is necessary to use Light or Dark mages to capture the kingdom, and to which cities they should be sent.
The first line of the input file contains the integers and (2 \leq N \leq 256, 2^K \geq N, K \leq N).
The next lines each contain integers. At the -th position of the -th line is the number , which means the city is not connected by a road to itself. For all j \neq i, the number at the -th position of the -th line is if the -th city is connected to the -th by a white road, and if they are connected by a black road. The numbers are separated by spaces.
It is guaranteed that the input data is correct: if the -th city is connected to the -th by a white road, then the -th city is also connected to the -th by a white road, and the same holds for black roads.
If it is impossible to capture the kingdom under the given conditions, output a single number .
Otherwise, in the first line, output if it is possible to capture the kingdom using Light mages, and if it is necessary to use Dark mages. In the next line, output the number L \leq K — the number of mages used. The third line should contain integers — the numbers of the cities to which the mages should be sent.
Note that you do not need to minimize . If there are multiple solutions, output any one of them.
Example 1