Олимпиадный тренинг

Задача . C. Нарисуйте дерево

Задача

Темы: геометрия Деревья Конструктив разделяй и властвуй сортировки *2200

Даны дерево с n вершинами и n точек на плоскости, никакие три из которых не лежат на одной прямой.

Вам надо нарисовать заданное дерево на плоскости, используя заданные точки в качестве вершин.

То есть каждой вершине дерева нужно сопоставить ровно одну точку, и каждая точка должна быть сопоставлена какой-либо вершине. Если две вершины дерева соединены ребром, между соответствующими точками должен быть нарисован отрезок. Отрезки, соответствующие несмежным ребрам, не должны иметь общих точек. Отрезки, соответствующие смежным ребрам, должны иметь ровно одну общую точку.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 1500) — количество вершин в дереве (оно же — количество выбранных точек на плоскости).

В следующих n - 1 строках через пробел записано по два целых числа u_i и v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — номера соединенных i-ым ребром вершин дерева.

В следующих n строках через пробел записано по два целых числа x_i и y_i ( - 10⁹ ≤ x_i, y_i ≤ 10⁹) — координаты i-ой точки на плоскости. Никакие три точки не лежат на одной прямой.

Гарантируется, что при заданных ограничениях задача имеет решение.

Выходные данные

Выведите n различных целых чисел от 1 до n через пробел: i-ое число должно равняться номеру вершины, которую надо поместить в i-ую точку (точки нумеруются в порядке их перечисления во входных данных).

Если существует несколько решений, выведите любое.

Примечание

Возможные ответы для примеров приведены ниже.