== include(page="template/taskheader" task_id="reinvent") ==

Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine $N$ case (numerotate de la $1$ la $N$) unite prin $M$ străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din $X$ case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele. Determinaţi distanţa minimă dintre două case distincte din cele $X$ din cartier.

Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine $N$ case (numerotate de la $1$ la $N$) unite prin $M$ străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din $X$ case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele.
 
Determinaţi distanţa minimă dintre două case distincte din cele $X$ din cartier.

h2. Date de intrare

3930