Masala #0968

Xotira 256 MB Vaqt 4000 ms
14

Shimoliy city

Quruvchi elflar va nihoyat Shimoliy citydagi barcha binolarni qurib bitkazishdi, endigi vazifa esa bu binolarni yo'llar orqali bog'lab chiqish. Qiyin tarafi esa yo'llarni Yangi yil bayramigacha bitkazish kerak, chunki Shimoliy qutbda asosiy bayramlarni yangi Shimoliy cityda o'tkazish rejalashtirilgan. Yo'llarni iloji boricha tez bitirish uchun esa hamma binolarni birlashtiruvchi eng qisqa yo'lni topish kerak.


Kiruvchi ma'lumotlar:

Sizga \(N\) natural soni va keyingi \(N\) ta qatorda \(X_i\)\(Y_i\) sonlari beriladi. \(X_i\)\(Y_i\) bu i-binoning joylashgan koordinatalari. Binolar 1 dan N gacha raqamlangan.
\(1\leq N \leq 1000;\)     \(-10^9 \leq X_i, Y_i \leq 10^9, \space i=\{1...N\}.\)


Chiquvchi ma'lumotlar:

Quruvchi elflarga eng qisqa yo'l uchun qaysi binolar o'rtasida yo'llar qurish kerakligini yozib bering. O'rtasida yo'l qurilishi kerak bo'lgan bino juftliklari sonini va keyingi qatorlarda juftliklarni probel bilan ajratgan holda alohida qatorlarda chop eting.
Agar bir necha xil javob mavjud bo'lsa, istalganini chop eting.


Misollar
# input.txt output.txt
1
5  
0 0
0 4
4 0
2 2
4 4
4
1 4
2 4
3 4
4 5
2
9
-10 5
-3 6
8 6
-4 1
4 2
0 0
-5 -8
2 -8
7 -9
8
4 6
5 6
2 4
8 9
3 5
7 8
1 2
6 8
Izoh:

Siz bergan javob va muallif javobidagi yo'l uzunliklari farqi \(10^{-6}\) dan katta bo'lganda javobingiz noto'g'ri deb hisoblanadi.