Cykly v síti
Zadání
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 u~i − 1~, pro 1 < i ≤ k. Z technických důvodů leží každý uzel sítě v nejvýše jednom cyklu.
Ú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říklady
Příklad 1
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 114 3 4 3Síť příkladu 1 je znázorněna na obrázku 1a).