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:

• ir iespējams atrast tieši vienu tādu virsotni, kurā neieiet neviena šķautne (to sauc par koka sakni),
• katrai virsotnei ir iespējams atrast tieši vienu ceļu pa šķautnēm, kas iet no saknes līdz šai virsotnei.

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!

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 vienīgajā rindā jāizvada koka saknes numurs un augstums. Ja ievadītais grafs nav koks, vienīgajā rindā jāizvada divi skaitļi 0. Starp skaitļiem jābūt vienam tukšumsimbolam.

Uzdevums izmantots Latvijas 16.informātikas olimpiādē 2003.gadā.