Республиканская олимпиада по информатике 2017 год, Павлодар

Задача E. Перевороты

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

На столе подряд лежат $K$ листов бумаги. Дано число $N$. На каждом листе записаны все числа от 1 до $N$ ровно по одному разу, но некоторые из них записаны на видимой стороне, а остальные на обратной. Ваша задача - перевернуть некоторые листы так, чтобы максимизировать количество различных чисел на видимых сторонах.

Формат входного файла

На первой строке даны $N$ и $K$, так чтобы $N \times K\le 10^6$ при этом $ N \ge 1 $ и $K \ge 1$. На следующих $K$ строках идут описания листов. На $i+1$ строке, первое число это $m$ ($0 \le m \le N$) — количество чисел записанных на видимой стороне $i$-ого листа бумаги. Далее идут $m$ чисел которые написаны на видимой стороне $i$-го листа, каждый от $1$ до $N$.

Формат выходного файла

Выведите строку состоящий из $K$ символов. $i(1 \le i \le K)$ символ равняется 1 если надо перевернут, иначе 0. Если существует несколько ответов, вывести любой.

Система оценки

Данная задача содержит пять подзадач:

1. $1 \leq N \leq 10$, $1 \le K \le 10$. Оценивается в $11$ баллов.
2. $1 \leq N \le K$. Оценивается в $8$ баллов.
3. $1 \leq N \leq 100$. Оценивается в $15$ баллов.
4. $1 \leq N \times K \leq 5 \cdot 10^4$. Оценивается в $30$ баллов.
5. $1 \leq N \times K \leq 10^6 $. Оценивается в $36$ баллов.

Примеры:

Вход

5 4
2 1 3
2 3 4
2 2 4
3 1 2 3

Ответ

1111

Вход

6 2
3 1 3 4
3 1 2 4

Ответ

01

( Temirlan Satylkhanov )