Cykly v síti

Počítačová síť podniku se skládá z uzlů a přímých spojení mezi některými dvojicemi uzlů. Síť je souvislá, což znamená, že mezi každými dvěma uzly může putovat signál oběma směry za použití jednoho nebo více přímých spojení.
Síť může obsahovat cykly. Cyklus je taková posloupnost u1, u2, ..., uk alespoň tří navzájem různých uzlů, ve které platí, že uzel uk je přímo spojen s uzlem u1 a dále každý uzel ui je přímo spojen s uzlem ui − 1, pro 1 < i ≤ k. Z technických důvodů leží každý uzel sítě v nejvýše jednom cyklu.

     


Obrázek 1. Ukázky topologie sítí. Síť 1a) odpovídá příkladu 1 níže, síť 1b) odpovídá příkladu 2 níže.

Úloha

Je dáno schéma sítě. Určete počet nejdelších a počet nejkratších cyklů v síti. Za délku cyklu považujeme vždy počet uzlů v cyklu.

Vstup

První řádek obsahuje dvě kladná celá čísla N a M oddělená mezerou a představující počet uzlů a počet přímých spojení v síti. Předpokládáme, že uzly sítě jsou označeny čísly 0, 1, ..., N − 1. Dále následuje M řádků, každý z nich určuje jedno přímé spojení. Na řádku jsou vždy uvedena čísla dvou uzlů oddělená mezerou. Pořadí uzlů na řádku a pořadí přímých spojení na vstupu je libovolné.
Platí N ≤ 106, M < 2 × 106.

Výstup

Na výstupu je jeden textový řádek se čtyřmi celými čísly A, B, C, D oddělěnými mezerou. A představuje délku nejkratšího cyklu v síti, B představuje počet nejkratších cyklů v síti, C představuje délku nejdelšího cyklu v síti, D představuje počet nejdelších cyklů v síti. Pokud síť žádné cykly neobsahuje, jsou všechny hodnoty A, B, C, D rovny nule.

Příklad 1

Vstup 
12 14
0 1
2 3
4 5
6 7
8 9
10 11
0 10
2 8
4 6
5 7
3 9
1 11
2 4
9 11
Výstup 
4 3 4 3
Síť příkladu 1 je znázorněna na obrázku 1a).

Příklad 2

Vstup 
19 22
1 2
4 5
5 6
6 7
11 12
16 17
17 18
3 13
4 14
0 3
0 4
9 11
9 12
13 15
14 15
1 5
2 8
6 10
7 10
5 17
8 17
12 14
Výstup 
3 2 6 1
Síť příkladu 2 je znázorněna na obrázku 1b).

Příklad 3

Vstup 
16 17
0 3
1 5
2 6
7 8
9 12
10 13
11 14
14 15
3 4
4 5
5 6
6 10
6 11
10 11
3 8
4 9
8 9
Výstup 
3 1 4 1

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data