The Conquest of the Kingdom
In a magical kingdom, there are N cities, each pair connected by a road. These roads were built in ancient times by the Light and Dark forces; roads built by the Light forces are paved with white stones, while those by the Dark forces are paved with black stones. Due to magical spells, 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 chose their rulers and expelled the supreme mages from the kingdom. However, recently, the supreme mages of the Light and Dark forces have agreed to reclaim control over the kingdom. To achieve this, they plan to send mages to certain cities to take control of these and the adjacent cities.
Specifically, if a Light mage is sent to a city, he will take control of that city and all cities directly connected to it by white roads. Similarly, a Dark mage will control the city he is sent to and all cities directly connected to it by black roads. To capture the kingdom, control over all cities must be established.
However, two challenges have arisen in the capture plan. First, a mage will only participate if all mages sent to the kingdom represent the same force as he does. That means either all mages must be Light or all must be Dark. Secondly, the total number of mages that can be sent to the kingdom must not exceed K.
The supreme mages hope that K is large enough, such that 2^K ≥ N.
Determine whether Light or Dark mages should be used to capture the kingdom, and identify which cities they should be sent to.
Input
The first line of the input file contains the integers N and K (2 ≤ N ≤ 256, 2^K ≥ N, K ≤ N).
The next N lines contain N integers each. At the i-th position of the i-th line is the number 0, indicating that the city is not connected by a road to itself. For all j ≠ i, the number at the j-th position of the i-th line is 1 if the i-th city is connected to the j-th by a white road and 2 if they are connected by a black road. The numbers in the lines are separated by spaces.
It is guaranteed that the input data is correct, meaning if the i-th city is connected to the j-th by a white road, then the j-th is also connected to the i-th by a white road, and similarly for black roads.
Output
If it is impossible to capture the kingdom under the given conditions, output a single number 0 in the output file.
Otherwise, in the first line, output 1 if it is possible to capture the kingdom using Light mages, and 2 if Dark mages need to be used. In the next line, output the number L ≤ K - the number of mages used. The third line should contain L integers - the numbers of the cities to which the mages should be sent.
Note that you do not need to minimize L. If there are multiple solutions, output any.