Dots orientēts grafs ar N virsotnēm. Virsotnes ir numurētas ar naturāliem skaitļiem no 1 līdz N. Orientētu grafu sauc par koku, ja vienlaicīgi ir izpildīti sekojoši nosacījumi:
To škautņu kopskaitu, pa kurām jāiet, lai nonāktu līdz virsotnei, sauc par šīs virsotnes dziļumu. Par dotā koka augstumu sauc lielāko virsotnes dziļumu.
Zīmējumā redzamajos orientēto grafu piemēros kreisais un vidējais ir koki, bet labējais nav. Kreisā koka sakne ir virsotne ar numuru 5 un augstums 2, bet kokam, kas atrodas vidū, sakne ir virsotne ar numuru 6 un augstums ir 5.
Uzrakstiet programmu, kas ievadītam grafam nosaka, vai tas ir koks, un, ja ir, atrod tā sakni un augstumu!
Teksta faila koks.dat pirmajā rindā doti divi veseli skaitļi N(1≤N≤1000) un M(0 ≤M≤1000), kas apzīmē attiecīgi grafa virsotņu un šķautņu skaitu. Starp skaitļiem ievaddatos ir viens tukšumsimbols. Nākošajās M faila rindās ir doti grafa šķautņu apraksti - katra šķautne aprakstīta savā rindā. Katra rinda satur divus naturālus skaitļus, kas atdalīti ar tukšumsimbolu. Pirmais skaitlis ir tās virsotnes numurs, no kuras šķautne iziet, bet otrs - tās virsotnes numurs, kurā šķautne ieiet.
Ja ievadītais grafs ir koks, tad teksta faila koks.rez vienīgajā rindā jāizvada koka saknes numurs un augstums. Ja ievadītais grafs nav koks, faila vienīgajā rindā jāizvada divi skaitļi 0. Starp skaitļiem jābūt vienam tukšumsimbolam.
| koks.dat | koks.rez |
6 5 6 2 5 4 6 3 5 1 5 6 |
5 2 |
| koks.dat | koks.rez |
3 3 1 2 2 3 3 1 |
0 0 |