Задача C. Comparison of graph layouts ≡

Условие

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

Пусть имеются два графа — исходный и считанный из файла. Из-за особенностей конвертации координаты вершин второго графа могли сместиться, но не более чем на заданное ε. Нумерация вершин также могла измениться.

Требуется сравнить указанные графы и по возможности восстановить соответствие между их вершинами между ними.

Формат входных данных

Во входных данных записано целое число N — размерность пространства, V — количество вершин и E — количество ребер.

После чего следует набор из N ⋅ V координат вершин исходного графа и набор из E его ребер, заданных парой целых чисел. Нумерация вершин начинается с нуля.

Далее аналогичным образом указан второй граф.

В конце входных данных указана используемая точность ε.

Формат выходных данных

Выходные данные должны содержать V целых чисел L_i — номер вершины второго графа, соответствующей i-й вершине исходного графа.

Если установить соответствия не представляется возможным, выведите единственное число  − 1.

Ограничения

Вершины исходного графа расположены друг от друга на расстоянии не менее чем 10 ⋅ ε, а их координаты лежат в диапазоне от  − 10 до 10.

1 ≤ N ≤ 5, 1 ≤ V ≤ 2 ⋅ 10⁴, 0 ≤ E ≤ 2 ⋅ V,

10^− 6 ≤ ε  ≤ 1

Примеры тестов

3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
 4.20000  3.65000 -4.23000
 1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
 1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
 4.20300  3.65001 -4.23079

0 3
2 0
3 1
2 3
1 2

0.1

2
0
3
1

3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
 4.20000  3.65000 -4.23000
 1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
 1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
 4.20300  3.65001 -4.23079

0 3
2 0
3 1
0 1
1 2

0.1

-1