전차 노선 색칠

한 도시의 전차망은 정류장과 정류장을 잇는 선로들로 이루어져 있다.

전차 노선 하나는 서로 다른 정류장들의 순서열로 주어진다. 같은 노선에서 이웃한 두 정류장 사이에는 직접 연결된 선로가 있다. 전체 전차망에서는 임의의 두 정류장을 잇는 경로가 정확히 하나이며, 전차를 이용해 어떤 정류장에서도 다른 정류장으로 이동할 수 있다.

각 전차 노선에 색을 칠하려고 한다. 같은 노선에 속한 전차들은 모두 같은 색을 사용하고, 하나의 정류장을 지나는 서로 다른 노선들은 모두 서로 다른 색이어야 한다.

사용하는 색의 수를 최소로 하는 색칠 방법을 구하라.

첫째 줄에 정류장 수 N과 전차 노선 수 M이 공백으로 구분되어 주어진다. 제한은 1 ≤ N ≤ 1000, 1 ≤ M ≤ 20000이다.

다음 M개의 줄에는 전차 노선의 설명이 주어진다. 각 설명은 먼저 그 노선이 지나는 정류장 수 R로 시작하고, 이어서 R개의 정류장 번호가 운행 순서대로 주어진다. 한 노선 안의 정류장 번호는 모두 다르다. 모든 수는 공백으로 구분된다.

입력 파일의 크기는 항상 2 MB보다 작다.

첫째 줄에 필요한 최소 색 수 B를 출력한다.

둘째 줄에 M개의 정수를 공백으로 구분해 출력한다. i번째 정수는 입력에서 i번째로 주어진 전차 노선의 색이다. 각 색은 1 이상 B 이하이어야 한다.

조건을 만족하는 최적 색칠 중 아무 것이나 출력해도 된다.