누가 쿠키를 가져올까?

농부 John의 소 $N$마리가 $1$번부터 $N$번까지 번호를 달고 $M$개의 스터디 그룹을 만들었습니다. 스터디 그룹 $i$에는 소 $S_i$마리가 속해 있습니다(한 소가 여러 스터디 그룹에 동시에 속할 수 있습니다).

각 스터디 그룹에서는 모임에 쿠키를 가져올 소 한 마리를 그 그룹의 구성원 중에서 반드시 정해야 합니다. 쿠키는 비싸고 준비하는 데 품이 들기 때문에, 소들은 이 부담을 최대한 공평하게 나누고 싶어 합니다.

어떤 소가 속한 스터디 그룹들의 크기가 각각 $c_1, c_2, \dots, c_K$라고 합시다(즉 그 소는 $K$개의 그룹에 속해 있고, 그중 $j$번째 그룹의 구성원 수가 $c_j$명입니다). 이때 그 소가 쿠키를 가져올 의향이 있는 모임 수는 최대

$\left\lceil \frac{1}{c_1} + \frac{1}{c_2} + \cdots + \frac{1}{c_K} \right\rceil$

회입니다.

각 스터디 그룹마다 쿠키를 가져올 소 한 마리를 배정하되, 어떤 소도 자신이 원하는 횟수보다 더 많은 모임에 배정되지 않도록 하세요.

제약: $1 \le N \le 1000$, $1 \le M \le 100$, $1 \le S_i \le 19$.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$째 줄까지: $i+1$째 줄은 스터디 그룹 $i$를 나타내며, $S_i$에 이어 그 그룹의 구성원 소 번호 $G_{i,1}, G_{i,2}, \dots, G_{i,S_i}$가 모두 공백으로 구분되어 주어집니다.

$M$개의 줄을 출력합니다. $i$째 줄에는 스터디 그룹 $i$에 쿠키를 가져오는 소의 번호 $a_i$를 출력합니다.

유효한 배정이 여러 개일 수 있으므로 사전순으로 가장 작은 배정을 출력하세요. 즉 $a_1$을 가능한 한 작게, 그런 배정들 중에서 $a_2$를 가능한 한 작게, 이런 식으로 정합니다.

유효한 배정이 존재하지 않으면 대신 $-1$ 하나만 한 줄에 출력합니다.

이 한도는 소가 맡은 모임이 얼마나 부담스러운지를 반영합니다. 큰 그룹의 구성원은 기여도 $1/c$가 작으므로 더 많은 모임을 감당할 수 있습니다.

예를 들어 크기가 각각 $2$, $3$, $1$인 그룹에 속한 소의 한도는 $\left\lceil \tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{1} \right\rceil = \lceil 1.833\ldots \rceil = 2$이므로, 그 소는 최대 $2$번의 모임에 쿠키를 가져올 의향이 있습니다. 크기가 $3$인 그룹 두 곳에 속한 소의 한도는 $\left\lceil \tfrac{1}{3} + \tfrac{1}{3} \right\rceil = 1$입니다.