Nosaukums
Tramvaju līnijas (tramvaji)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

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ā!

Ievaddatu raksturojums

Ievaddatu 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 apjoms nepārsniedz 2MB.

Izvaddatu raksturojums

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

Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā

Paraugdati

Stdin
6 3
3 1 2 3
3 4 5 6
4 1 2 5 6
Stdout
2
Stdin
6 4
6 1 2 3 4 5 6
3 2 3 4
2 5 4
2 5 6
Stdout
3
Stdin
8 4
3 3 2 1
3 2 5 6
4 4 5 6 7
2 8 4
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.