Šeštadieninė informatikos olimpiadininkų mokykla

Cinkiškių kaimas kenčia nuo transporto kamščių (jau nebe kaimas, turbūt). Savivaldybė bandė įvairius šios problemos sprendimo būdus, tačiau niekas nepadėjo. Pagaliau jie nusprendė nutiesti papildomų kelių. Tačiau nauji keliai turi būti naudojami. Jie bus naudojami tuo atveju, jei atstumas tarp kokių nors sankryžų taps mažesnis.

Jums duotas Cinkiškių planas ir Jūs turite pasiūlyti pirmą kelią tiesimui. Sankryžos sunumeruotos nuo 1 iki N. Kelias tarp sankryžų a ir b gali būti tiesiamas, jei tarp tų sankryžų dar nėra kelio. Kiekvienam būsimam keliui, jo vertė ), kur yra atstumas tarp sankryžų i ir j dabar, o yra atstumas tarp i ir j nutiesus kelią tarp a ir b. Raskite kelią, kurio vertė didžiausia. Jei yra keletas variantų, tai pasirinkite trumpesnį kelią. Jei dar yra keli variantai, pasirinkite tą, kurio mažesnio numerio sankryžos numeris yra mažesnis. Vis dar esant keliems variantams, rinkitės tą, kurio didesnio numerio sankryžos numeris yra mažesnis.

Pradiniai duomenys

Pirmoje eilutėje yra du sveikieji skaičiai N (), sankryžų kiekis, ir M (), kelių kiekis. Tolesnėse eilutėse yra N sveikųjų skaičių porų. Pirma pora yra sankryžos nr. 1 koordinatės, antra pora - sankryžos nr. 2 ir t.t. Kiekviena koordinatė yra sveikas skaičius tarp -1000 ir 1000. Tolesnėse keliose eilutėse yra M sveikųjų skaičių porų. Kiekviena pora reiškia dvi sankryžas, kurios yra sujungtos keliu. Visada yra galimybė patekti iš bet kurios sankryžos į bet kurią kitą.

Rezultatai

Vienoje eilutėje du skaičiai u ir v (), kurie reiškia, kad reikia tiesti kelią tarp sankryžų u ir v, arba 0, jei vertingiausio kelio vertė nesiekia 1.

Pavyzdys

4 4
0 0 0 2
2 0 2 2
1 2
2 3 3 4
4 1

1 3