유일한 해

시간 제한1초메모리 제한1024 MB

요약

각 문제의 후보가 5개 이하이고 전체가 완전 매칭을 이루는 상황에서, 매칭이 유일한지 판정하고 유일하면 답을 출력한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그래프, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

국렬이는 위상수학 기말고사에서 고통을 받고 있다. 위상수학 교수님이 특이하셔서 문제 수가 $N$ 개에 답이 될 수 있는 경우가 $N$ 개가 있지만, 각 문제마다 답이 겹치는 경우는 없다.

예를 들어서 문제가 5개면 보기가 1, 2, 3, 4, 5가 있으며, 1번 문제의 답이 3이면 다른 문제에서는 답이 3인 경우는 없다.

그러나 국렬이의 수학 실력은 뛰어나지 않아서 각 문제마다 답이 될 수 있는 보기들을 유일하게 정할 수 없게 되었다. 그래도 각 문제마다 최소 1개에서 최대 5개의 정답이 될 수 있는 후보군들을 지니고 있다. 주어지는 후보군들 중에서 무조건 답이 존재한다고 가정한다.

후보군들의 정보를 받았을 때, 해당 후보군만으로 모든 문제의 답을 유일하게 정할 수 있는지를 알아보자.

입력

첫 번째 줄에는 문제의 개수를 의미하는 정수 $N$ ( $4 \le N \le 1{,}000$ )이 주어진다.

두 번째 줄부터 $N + 1$ 번째 줄까지 정답의 후보군에 대한 정보가 들어온다. $i + 1$ 번째 줄에는 정수 $A_i$ ( $1 \le A_i \le 5$ )와 $A_i$ 개의 정수가 입력된다. $A_i$ 는 $i$ 번째 문제의 정답의 후보군의 개수며, 뒤의 정수는 정답의 후보군들이다. 후보군들은 서로 다른 정수로, 1부터 $N$ 까지의 정수다.

출력

만약에 해당 후보군만으로 모든 문제의 답을 유일하게 정할 수 있으면 첫 번째 줄에 1을 출력하고, 그 다음 줄에 각 문제에 대한 정답 $N$ 개를 1번 문제부터 순서대로 공백으로 구분해서 출력한다. 유일하게 결정할 수 없는 경우라면 첫 번째 줄에 -1을 출력한다.

예제2

예제 1
입력
```
4
1 2
2 2 3
2 3 4
2 4 1
```
예상 출력
```
1
2 3 4 1
```
예제 2
입력
```
4
2 1 2
2 2 3
2 3 4
2 4 1
```
예상 출력
```
-1
```