SP3413 SAMER08I - Traveling Shoemaker Problem

Once upon a time there was a very peaceful country named Nlogonia. Back then, Poly the Shoemaker could come to the country and travel freely from city to city doing his job without any harassment. This task was very easy, as every city in Nlogonia had a direct road to every other city in the country. He could then easily travel the whole country visiting each city exactly once and fixing everybody's shoes. But not anymore. The times have changed and war has come to Nlogonia. The age when people could travel freely is over. Confederations identified by colors were formed among the cities all over the country, and now each city belongs to at least one and at most two confederations. When trying to enter a city, you must give to the border officer a ticket from one of the confederations this city belongs to. When leaving the city, you receive a ticket from the other confederation the city belongs to (i.e. different from the one you gave when entering) or from the same confederation if the city only belongs to one. As Poly the Shoemaker is a long time friend of Nlogonia, he is allowed to choose a ticket and a city he wants to enter as the first city in the country, but after that he must obey the confederations rules. He wants to do the same routine he did before, visiting each city exactly once in Nlogonia, but now it's not easy for him to do this, even though he can choose where to start his journey. For example, suppose there are four cities, labeled from 0 to 3. City 0 belongs to confederations _red_ and _green_; city 1 belongs only to _red_; city 2 belongs to _green_ and _yellow_; and city 3 belongs to _blue_ and _red_. If Poly the Shoemaker chooses to start at city 0, he can enter it carrying either the _red_ or the _green_ ticket and leave receiving the other. Should he choose the _red_ ticket, he will leave with a _green_ ticket, and then there is only city 2 he can travel to. When leaving city 2 he receives the _yellow_ ticket and now can't go anywhere else. If he had chosen the _green_ ticket as the first he would receive the _red_ one when leaving, and then he could travel to cities 1 or 3. If he chooses city 3, when leaving he will receive the _blue_ ticket and again can't go anywhere else. If he chooses city 1, he receives the _red_ ticket again when leaving (city 1 belongs only to the _red_ confederation) and can only travel to city 3 and will never get to city 2. Thus, it is not possible to visit each city exactly once starting at city 0. It is possible, however, starting at city 2 with the _yellow_ ticket, leaving the city with the _green_ ticket, then visiting city 0, leaving with _red_ ticket, then visiting city 1, leaving with _red_ ticket again and, at last, visiting city 3. As you can see, it got really difficult for Poly the Shoemaker to accomplish the task, so he asks you to help him. He wants to know if it's possible to choose a city to start such that he can travel all cities from Nlogonia exactly once. Can you help Poly the Shoemaker?

The input contains several test cases. The first line of a test case contains two integers _N_ and _C_, separated by one space, indicating respectively the number of cities (1 N C C lines describes a confederation. It starts with one integer _K_ (0 K N) and then _K_ integers representing the cities which belong to this confederation. All integers are separated by single spaces and cities are numbered from 0 to _N_ -1. Each city will appear at least once and at most twice and no city will be repeated on the same confederation. The end of input is indicated by a line containing two zeroes separated by a single space.

For each test case in the input, your program must print a single line, containing the integer -1 if it's not possible to match the requirements or one integer representing the city where Poly the Shoemaker can start his journey. If there are multiple correct answers, print the smallest one.