Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

The following languages are only available languages for the problems from the contest

VK Cup 2015 - Wild Card Round 1:

- Picat 0.9

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

I. Different variables

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard output*N* variables *X*_{1}, ..., *X*_{N} can have positive integer values. You are given *K* constraints for these value that look like "the values of variables *X*_{i1}, *X*_{i2}, ..., *X*_{iM} are different". Among all possible lists of values of these variables that satisfy these constraints select the ones which have minimum possible *max*(*X*_{i}). Output lexicographically least of these lists.

Input

The first line of input contains two integers *n* and *k* (2 ≤ *N* ≤ 10, 1 ≤ *K* ≤ 100) — the number of variables and the number of constraints.

The following *K* lines contain the constraints, formatted as follows: the first number in the line *M* (2 ≤ *M* ≤ *N*) gives the number of variables in the constraint. After it follow *M* space-separated integers *i*_{1}, ..., *i*_{M} — the indices of the variables used in the constraint (1 ≤ *i*_{j} ≤ *N*). All *i*_{j} in one constraint are different.

Output

Output the values of *X*_{1}, *X*_{2}, ..., *X*_{N} in a single line, separated with single spaces.

Examples

Input

2 1

2 1 2

Output

1 2

Input

3 2

2 1 2

2 2 3

Output

1 2 1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 01:02:58 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|