Poloměr komponent grafu

V této úloze uvažujeme prosté neorientované grafy bez smyček. Pro přehlednost nejprve připomeneme standardní definice teorie grafů.

• Cesta délky d (d ≥ 0) mezi uzly a a b v grafu G = (V, E) je taková neprázdná posloupnost jeho uzlů (a = x₀, x₁, x₂, ..., x_d = b), ve které platí
  1. 0 < i ≤ d ⇒ {x_i−1, x_i} ∈ E.
  2. 0 ≤ i < j ≤ d ⇒ x_i ≠ x_j.
• Graf G prohlásíme za souvislý, pokud mezi každými dvěma uzly v G existuje alespoň jedna cesta.
• Komponenta grafu G je takový souvislý podgraf G, který není obsažen v žádném větším (vzhledem k inkluzi) souvislém podgrafu G.
• Vzdálenost dvou uzlů v souvislém grafu je definována jako délka nejkratší cesty mezi nimi.
• Excentricita uzlu v souvislém grafu je definována jako vzdálenost mezi tímto uzlem a uzlem jemu v grafu nejvzdálenějším.
• Uzel s minimální excentricitou se nazývá střed grafu (obecně středů grafu může být více).
• Poloměr souvislého grafu je definován jako excentricita jeho libovolného středu.

Úloha
Na vstupu je dán graf, je třeba určit počet jeho komponent a maximální hodnotu poloměru všech jeho komponent.

Vstup

Na vstupu jsou tři kladná celá čísla N₁, N₂ a D zapsaná na jednom řádku a oddělená navzájem vždy jednou mezerou. Zkoumaný graf je určen takto:
Uzly grafu jsou všechna přirozená čísla z množiny {N₁, N₁+1, N₁+2, ..., N₂}. Dva uzly a, b jsou spojeny hranou právě tehdy, když
NSD(a + b + |a − b| + 3, a × b + |a − b| + 2) ≥ D.
Platí N₂ ≤ 10⁹, 0 ≤ N₂ − N₁ ≤ 1000, 1 ≤ D ≤ 10⁴.

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í poloměr všech komponent grafu (pokud je graf souvislý, je druhým číslem poloměr celého grafu).

Příklad 1

Vstup:

10 20 3

Výstup:

5 2

     

Obr. 1. Graf zadaný v příkladu 1, středy největší komponenty jsou 11, 15, 18.

Příklad 2

Vstup:

10 20 1

Výstup:

1 1

Graf zadaný v příkladu 2 je úplný graf s 11 uzly.

Příklad 2

Vstup:

111100001 111100999 26

Výstup:

163 5

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