Průměr grafu

Zadání: http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=prumergrafu

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.

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 N2 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.

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).

Vstup:

2 7 4 1

Výstup:

1 3

Vstup:

5 11 4 2

Výstup:

1 2