The Rice Cake Seller and the Tiger

Interview

Time limit1sMemory limit128 MB

Summary

Pick one rice cake kind from each day's set so consecutive picks differ; output the daily picks or -1 if impossible.

Level: Easy3 of 10
Topics: Dynamic programming, Backtracking, Implementation
Solved: No attempts yet

Problem

Every dawn, the rice cake seller Donghee carries freshly made rice cakes over the mountain to the market and sells them. The kinds of rice cakes Donghee makes are numbered 1 through 9.

A tiger lives on the mountain. It waits for Donghee to appear, threatens him, and takes one rice cake. This tiger is picky: if the rice cake is the same kind as the one it ate the day before, it will not eat it. If Donghee has no rice cake to give, the tiger eats him.

Donghee must go to the market every day for N days to sell rice cakes. The kinds of rice cakes Donghee makes change each day depending on the supply of ingredients.

Choose the rice cakes Donghee should give the tiger so that he is not eaten over the N days.

Input

The first line gives N (1 ≤ N ≤ 1,000), the number of days Donghee must sell rice cakes.

Line i+1 (1 ≤ i ≤ N) gives mi, ai,1, ai,2, ..., ai,mi (1 ≤ mi ≤ 9, 1 ≤ ai,1 < ai,2 < ... < ai,mi ≤ 9), where mi is the number of rice cakes Donghee carries on day i and ai,j is the kind of a rice cake he carries.

Output

If there is a way for Donghee to give the tiger rice cakes over the N days, print on line i (1 ≤ i ≤ N) the rice cake Donghee must give the tiger. This rice cake must be one Donghee made on day i.

If there is no way for Donghee to give rice cakes, print only '-1' on the first line and print nothing else.

If there are multiple ways, print any one of them.

Examples2

Example 1
Input
```
3
3 1 2 3
2 1 2
2 2 3
```
Expected output
```
2
1
3
```
Example 2
Input
```
3
3 7 8 9
1 1
1 1
```
Expected output
```
-1
```