Tram Line Coloring

A city's tram network consists of stations and track segments connecting stations.

Each tram line is given as a sequence of distinct stations. Consecutive stations on the same line are directly connected by a track segment. In the whole network, there is exactly one route between any two stations, and it is possible to travel from every station to every other station by tram.

We want to assign a color to each tram line. All trams on the same line use the same color, and any two different lines that pass through the same station must have different colors.

Find a coloring that uses as few colors as possible.

The first line contains two integers N and M separated by a space: the number of stations and the number of tram lines. The limits are 1 ≤ N ≤ 1000 and 1 ≤ M ≤ 20000.

Each of the next M lines describes one tram line. A description starts with an integer R, the number of stations on that line, followed by the R station numbers in travel order. The station numbers within one line are all distinct. All numbers are separated by spaces.

The input file is always smaller than 2 MB.

On the first line, output B, the minimum number of colors needed.

On the second line, output M integers separated by spaces. The i-th integer is the color assigned to the i-th tram line from the input. Each color must be between 1 and B, inclusive.

You may output any optimal coloring that satisfies the conditions.