Průměr grafu

Na vstupu je dán prostý neorientovaný graf bez smyček, je třeba určit počet jeho komponent a velikost průměru komponenty s největším průměrem.

Průměr grafu, pokud je souvislý, je roven vzdálenosti mezi dvěma navzájem nejvzdálenějšími uzly v grafu (takových uzlů může být případně v grafu více). Vzdálenost mezi dvěma uzly je délka nejkratší cesty mezi nimi, přičemž délka cesty je rovna počtu hran v cestě. Uvažujeme graf s alespoň dvěma uzly.

Vstup

Na vstupu jsou čtyři kladná celá čísla N₁, N₂, D a HD zapsaná na jednom řádku a oddělená navzájem vždy jednou mezerou. Vrcholy grafu jsou všechna přirozená čísla z množiny {N₁, N₁+1, N₁+2, ..., N₂}. Hrany grafu jsou konstruovány takto: Každý uzel reprezentujeme jako binární číslo zapsané pomocí přesně D znaků 0/1. Pokud je číslo dostatečně malé, jeho zápis obsahuje příslušný počet úvodních nul. Dva uzly jsou spojeny hranou, pokud Hammingova vzdálenost těchto jejich zápisů je menší nebo nejvýše rovna HD. Hodnota D je nejvýše 62, hodnota N₂ je nejvýše 2^D−1, hodnota N₁ je vždy alespoň o 2 a nejvýše o 5000 menší než N₂. Hodnota HD se pohybuje v rozmezí od 1 do 5.

Výstup

Na výstupu jsou dvě čísla v jednom řádku oddělená mezerou. První určuje počet komponent zadaného grafu, druhé určuje maximální průměr ze všech komponent grafu (pokud je graf souvislý, je druhým číslem průměr celého grafu).

Příklad 1

Vstup:

2 7 4 1

Výstup:

1 3

Příklad 2

Vstup:

5 11 4 2

Výstup:

1 2