Дерева Гамп#9751
Високі дерева в джумбарських джунглях мають важливе стратегічне значення. Штаб джумбарської армії вибрав дерев, розташованих відносно близько один до одного, і вирішив побудувати на кожному з них будиночок, в якому буде розміщено по одному армійському підрозділу.
Переміщення особового складу та вантажів між вершинами дерев буде забезпечуватися системою двонапрямлених канатних доріг, що з'єднують пари будиночків. З міркувань безпеки жодні дві канатні дороги не повинні перетинатися (при спостереженні зверху).
Усього вже вибрано армійських підрозділів, і складено список пар підрозділів. Підрозділи в кожній парі передбачається розмістити на протилежних кінцях однієї канатної дороги. Список містить рівно n - 1 пару. Гарантується, що цей список забезпечує зв'язність всієї території, тобто після розміщення підрозділів на деревах будь-який підрозділ зможе дістатися до будь-якого іншого, використовуючи лише канатні дороги зі списку.
Залишається лише встановити канатні дороги між будиночками таким чином, щоб розміщення підрозділів задовольняло вказаним вище вимогам.
Перша строка містить одне ціле число n~(1 \le n \le 1000) — кількість вершин дерев і армійських підрозділів. І вершини дерев, і підрозділи пронумеровані числами 0, 1, \dots, n - 1.
Наступні n - 1 рядків описують список пар підрозділів. Кожен рядок містить два цілі числа — номери двох підрозділів, які повинні знаходитися на протилежних кінцях однієї канатної дороги.
Наступні рядків містять координати обраних вершин дерев. В (i + 1)-му з цих рядків записані два цілі числа x_i і y_i~(0 \le x_i, y_i \le 10^9) — координати вершини дерева з номером . Гарантується, що жодні три вершини дерев не лежать на одній прямій.
Виведіть список усіх пар вершин дерев, які необхідно з'єднати канатними дорогами. Список повинен складатися з n - 1 рядка, кожен з яких містить номери двох різних дерев.
Якщо існує декілька допустимих рішень, виведіть будь-яке з них.
Приклад 1
Приклад 2