Tramvaju līnijas

Uzdevums

Pilsētas tramvaju līniju tīklu veido pieturas un sliežu posmi, kas tās savieno.

Katra tramvaju līnija sastāv no dažādu staciju virknes, kur katras divas pēc kārtas esošas pieturas savā starpā savieno sliežu posms. Katras divas pieturas var savienot tikai viens sliežu posms. Vienmēr ir iespējams nokļūt no vienas pieturas uz jebkuru citu, izmantojot tikai tramvaja līnijas.

Katrs tramvajs brauc pa savu līniju un pilsētas vadība ir nolēmusi nokrāsot katru tramvaju noteiktā krāsā, ievērojot sekojošo:

• visiem vienas līnijas tramvajiem jābūt vienā krāsā;
• ja dažādu līniju tramvaji brauc caur vienu pieturu, tiem jābūt nokrāsotiem atšķirīgās krāsās.

Uzrakstiet programmu, kas nosaka, kāds ir mazākais krāsu skaits, kāds nepieciešams, lai nokrāsotu tramvajus iepriekšaprakstītajā veidā!

Ievaddati

Teksta faila tramvaji.dat pirmajā rindā dotas divu naturālu skaitļu N (pieturu skaits,1 ≤N≤1000) un M (līniju skaits, 1≤M≤20000) vērtības, kas atdalītas ar tukšumsimbolu. Pieturas tiek numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas.

Nākošajās M faila rindās dots tramvaja līniju apraksts - pa vienas līnijas aprakstam katrā rindā.

Katras rindas pirmais skaitlis ir pieturu skaits šajā līnijā, kam seko pieturu numuri (ieskaitot gala pieturas). Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.

Piezīme: Ievaddatu faila izmērs nepārsniedz 2MB.

Izvaddati

Teksta faila tramvaji.rez vienīgajā rindā jāizvada mazākais krāsu skaits, kādā iespējams nokrāsot tramvajus.

Piemērs

tramvaji.dat	tramvaji.rez
6 3 3 1 2 3 3 4 5 6 4 1 2 5 6	2
tramvaji.dat	tramvaji.rez
6 4 6 1 2 3 4 5 6 3 2 3 4 2 5 4 2 5 6	3
tramvaji.dat	tramvaji.rez
8 4 3 3 2 1 3 2 5 6 4 4 5 6 7 2 8 4	2

Atsauces