여행하는 구두 수선공

옛날 옛적에 Nlogonia라는 아주 평화로운 나라가 있었다. 그때 구두 수선공 Poly는 아무런 방해 없이 도시에서 도시로 자유롭게 다니며 일을 할 수 있었다. Nlogonia의 모든 도시는 다른 모든 도시와 직접 연결된 도로를 가지고 있었기 때문에, 각 도시를 정확히 한 번씩 방문하며 모두의 구두를 고치는 일은 아주 쉬웠다.

하지만 이제는 그렇지 않다. 시대가 바뀌어 Nlogonia에 전쟁이 찾아왔고, 자유롭게 이동하던 시절은 끝났다.

색으로 구분되는 연합(confederation) 들이 도시들 사이에 만들어졌고, 이제 각 도시는 최소 한 개, 최대 두 개의 연합에 속한다. 어떤 도시에 들어갈 때에는 그 도시가 속한 연합 중 하나의 티켓을 국경 관리에게 내야 한다. 그 도시에서 나올 때에는 그 도시가 속한 다른 연합(들어갈 때 낸 것과 다른 연합)의 티켓을 받는다. 만약 그 도시가 한 개의 연합에만 속한다면 같은 연합의 티켓을 받는다.

Poly는 Nlogonia의 오랜 친구이므로, 가장 먼저 들어갈 도시와 그때 사용할 티켓을 자유롭게 고를 수 있다. 그러나 그 이후에는 위 규칙을 지켜야 한다. 그는 예전처럼 모든 도시를 정확히 한 번씩 방문하고 싶어 하며, 어디에서 시작할지는 마음대로 정할 수 있다.

예를 들어 도시가 네 개 있고 $0$부터 $3$까지 번호가 매겨져 있다고 하자. 도시 $0$은 빨강과 초록에, 도시 $1$은 빨강에만, 도시 $2$는 초록과 노랑에, 도시 $3$은 파랑과 빨강에 속한다. Poly가 도시 $0$에서 시작한다면, 빨강 또는 초록 티켓으로 들어가 다른 하나를 받고 나온다. 빨강으로 들어가면 초록을 받고 나오며, 그다음 갈 수 있는 곳은 도시 $2$뿐이다. 도시 $2$에서 나오면 노랑을 받아 더는 아무 데도 갈 수 없다. 만약 초록으로 들어갔다면 빨강을 받고 나와 도시 $1$ 또는 $3$으로 갈 수 있다. 도시 $3$을 고르면 파랑을 받고 나와 다시 막힌다. 도시 $1$을 고르면 (도시 $1$은 빨강에만 속하므로) 다시 빨강을 받고 나와 도시 $3$으로만 갈 수 있어 도시 $2$에는 결코 도달하지 못한다. 따라서 도시 $0$에서 시작해서는 모든 도시를 정확히 한 번씩 방문할 수 없다. 그러나 도시 $2$에서 노랑 티켓으로 시작하면, 초록을 받고 나와 도시 $0$을 방문하고, 빨강을 받고 나와 도시 $1$을 방문하고, 다시 빨강을 받고 나와 마지막으로 도시 $3$을 방문할 수 있다.

Poly가 시작 도시를 잘 골라서 Nlogonia의 모든 도시를 정확히 한 번씩 방문할 수 있는지 판단하도록 도와주자.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 $N$과 연합의 수 $C$가 공백으로 구분되어 주어진다 ($1 \le N \le 500$, $1 \le C \le 100$). 이어지는 $C$개의 줄은 각각 하나의 연합을 설명한다. 각 줄은 정수 $K$ ($0 \le K \le N$)로 시작하고, 그 뒤에 그 연합에 속하는 $K$개의 도시 번호가 온다. 도시는 $0$부터 $N-1$까지 번호가 매겨진다. 모든 도시는 적어도 한 번, 많아야 두 번 등장하며, 같은 연합 안에서 같은 도시가 중복되지 않는다. 한 줄의 모든 정수는 하나의 공백으로 구분된다.

입력의 끝은 두 개의 0이 공백으로 구분된 줄(0 0)로 나타낸다.

각 테스트 케이스마다 한 줄을 출력한다. 규칙을 지키며 모든 도시를 방문하는 것이 불가능하면 $-1$을, 가능하면 Poly가 시작할 수 있는 도시의 번호를 출력한다. 조건을 만족하는 도시가 여러 개라면 가장 작은 번호를 출력한다.