Qamp Ağacları#9751
Cümbarski cəngəlliklərindəki hündür ağaclar strateji baxımdan mühüm əhəmiyyətə malikdir. Cümbarskı ordusunun qərargahı nisbətən yaxın yerləşən ağac seçdi və əskər birləşməsini yerləşdirmək üçün hər birinə bir ev tikməyə qərar verdi.
Şəxsi heyətin və yüklərin ağacların zirvələri arasında hərəkəti, evləri bir birinə bağlayan cütlər arasında ikitərəfli kanat yolları sistemi ilə təmin ediləcək. Təhlükəsizlik səbəbindən üstən baxıldığında heç bir iki kanat yolu kəsişməməlidir.
Artıq hərbi birləşmə seçilib və birləşmə cütlərinin siyahısı hazırlanıb. Hər bir birləşmə cütü bir kanat yolunun əks uclarında yerləşəcək. Siyahı dəqiq n - 1 cütdən ibarətdir. Bu siyahının bütün ərazinin əlaqəli olmasını təmin etdiyinə zəmanət verilir, yəni birləşmələr ağaclara yerləşdirildikdən sonra hər bir birləşmə yalnız siyahıda göstərilən kanat yollarından istifadə edərək, digər birləşməyə çata biləcək.
Qalır yalnız birləşmələrin yerləşdirilməsi yuxarıda göstərilən tələblərə uyğun olaraq evləri kanat yolları ilə birləşdirməkdir.
Birinci sətir yeganə tam ədəd n (1 \le n \le 1000) — ağac zirvələrinin və hərbi birləşmələrin sayı. Həm ağac zirvələri, həm də bölmələr 0, 1, \dots, n - 1 rəqəmləri ilə nömrələnib.
Sonraki n - 1 sətir birləşmə cütlərinin siyahısını təsvir edir. Hər bir sətir iki tam ədəd ehtiva edir — kanat yolunun əks uclarında yerləşməli olan iki birləşmənin nömrəsi.
Sonraki sətir seçilmiş ağac zirvələrinin koordinatlarını ehtiva edir. Bu sətirlərin (i + 1)-ci sətiri iki tam ədəd x_i və y_i (0 \le x_i, y_i \le 10^9) ehtiva edir — nömrəli ağacın zirvəsinin koordinatları. Heç bir üç ağac zirvəsinin bir düz xətt üzərində olmadığına zəmanət verilir.
Kanat yolları ilə birləşdirilməli olan bütün ağac zirvələrinin cütlərinin siyahısını cetdirin. Siyahı n - 1 sətirdən ibarət olmalı və hər birində iki fərqli ağacın nömrələri olmalıdır.
Əgər bir neçə uyğun həll yolu varsa, onlardan hər hansı birini cetdirin.
Nümunə 1
Nümunə 2