time limit per test: 0.25 sec. memory limit per test: 4096 KB
input: standard output: standard
Microland country has very big territory, so its citizens always travel by air between cities. This is why transporting people by air is very profitable in Microland, and some years ago there was exactly one direct air flight between any two cities and there had survived only one air company, "Microland airlines". But then some Microland states suited it for violating the antitrust law and, according to the decision of the court, that company was divided into M independent parts, which later become known as "Microland airlines 1", "Microland airlines 2" and so on. Every flight previously owned by "Microland airlines" became owned by exactly one of its parts.
Now the president elections are coming in this country. To increase his rating, current president of Microland decided to buy some parts of "Microland airlines" and make flights of these companies free. He wants to make it easier to travel from any city to any, so for any two cities he wants to make it able to fly from one to other making not more than 2 changes, i.e. using not more than 3 free flights. In other words, for any two cities A and B: direct flight between these cities must be done free, or there must exist a city C so that flights from A to C and from C to B will be done free, or there must exist two cities C and D so that flights from A to C, from C to D, from D to B will be done free. But, of course, the president is avoid of breaking that antitrust law (the court is really independent in Microland!). Not to violate it, president has to buy not more than ((M+1) div 2) "Microland airlines" parts.
You are working in president's team. You are to write a program that will decide, what parts of "Microland airlines" the president should buy.
On the first line of input there are two integers N and M (1<=N<=200) --- the number of cities in Microland and the number of "Microland airlines" parts. Next N lines contain N integers each. i-th integer in i-th line is 0; and j-th, if j<>i, is the number of "Microland airlines" part which owns direct flight from i-th city to j-th (and from j-th to i-th too). Each "Microland airlines" part owns at least one flight.
If the solution exists, write on the first line of output one integer --- the number of "Microland airlines" parts that should be bought by president. On the second line of output write the numbers of these parts in any order. If several solutions exist, output any. If no solutions exist, output only one integer "-1".
4 3 0 3 2 2 3 0 1 2 2 1 0 1 2 2 1 0
2 1 3
NNSU #2 team
Lazurny olympiad in informatics, 2002
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov