ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2000

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Central Heating

Time limit: 1.0 second
Memory limit: 64 MB
Winter has come, but at the Ural State University heating is not turned on yet. There’s one little problem: the University is heated only if all of the valves are opened. There are some technicians at the University. Each of them is responsible for one or more valves. There may be several technicians responsible for the same valve. When a technician gets an instruction to turn on the heating he goes round all of his valves and turns them. It means that if a valve was opened then he closes it, and if it was closed then he opens it. It is well known that every technician earns his money not in vain so it’s impossible to replace any technician by any combination of other technicians.
Your task is to determine who of the technicians is to get an instruction “to turn on the heating” in order to heat all the Ural State University. Note that there are N technicians and N valves at the University.


The first line contains an integer N (1 ≤ N ≤ 250). The next N lines contain lists of the valves in charge of each of the technicians. It means that the line number i + 1 contains numbers of the valves that the i-th technician is responsible for. Each list of valves is followed by –1.


Output a list of technicians’ numbers sorted in ascending order. If several lists are possible, output the shortest one. If it’s impossible to turn on the heating at the University, output “No solution”.


1 2 -1
2 3 4 -1
2 -1
4 -1
1 2 3
Problem Author: Evgeny Shtykov
Problem Source: Ural State University Internal Contest October'2000 Students Session
To submit the solution for this problem go to the Problem set: 1042. Central Heating