Синій ліс#3602

Синій ліс

30 секунд

256 мегабайтів

Дуже складна

Джон грає у відому консольну гру під назвою 'Tales of Algorithmers.' Зараз він стоїть перед останнім підземеллям під назвою 'Синій Ліс.' Щоб знайти найшвидший шлях через це складне підземелля, він вирішив намалювати карту.

Підземелля складається з кількох поверхів, кожен з яких можна описати як зв'язний простий планарний граф. Вершини графа визначаються координатами $X$ - $Y$ , а довжина ребра обчислюється за допомогою евклідової відстані. Деякі вершини можуть бути обладнані односторонніми варп-воротами. Якщо Джон вирішить скористатися воротами, вони перенесуть його до іншої вершини, можливо, на іншому поверсі. Відстань між варп-воротами та їх призначенням вважається $0$ .

Кожна вершина може мати не більше одного варп-ворота, хоча деякі вершини можуть бути призначенням для кількох варп-воротів.

Джон вважає, що намалював одну карту для кожного поверху, але після завершення він помітив, що міг зробити кілька помилок. Він міг намалювати один і той самий поверх кілька разів і міг забути позначити деякі варп-ворота на картах. Однак він впевнений, що позначив усі варп-ворота хоча б один раз. Тому, якщо карти одного і того ж поверху об'єднати в одну карту, всі варп-ворота повинні бути описані там. На щастя, немає поверхів, які мають таку ж форму, як інші поверхи, тому якщо дві (або більше) карти можуть бути об'єднані, вони повинні бути картами одного і того ж поверху. Також немає поверху, який є круговим симетричним (наприклад, правильний трикутник і квадрат).

Карта $A$ і карта $B$ можуть бути об'єднані, якщо карту $B$ можна перетворити на карту $A$ за допомогою лише обертання та паралельного переносу. Оскільки деякі з варп-воротів на картах можуть бути відсутні, ви не повинні враховувати існування варп-воротів при перевірці об'єднання. Якщо можливо об'єднати карту $A$ і карту $B$ , вершина на карті $A$ і відповідна вершина на карті $B$ вважаються 'ідентичними' вершинами. Іншими словами, ви повинні розглядати варп-ворота на карті $B$ як ті, що на карті $A$ , де варп-ворота розташовані на відповідних вершинах на карті $A$ . Призначення варп-воротів слід обробляти аналогічно. Після цього ви можете забути карту $B$ . Гарантується, що якщо і карта $A$ , і карта $B$ мають варп-ворота, які знаходяться на ідентичних вершинах, їх призначення також ідентичні.

Ваше завдання - знайти найкоротший шлях від входу до виходу з підземелля, використовуючи об'єднані карти.

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір даних має наступний формат.

$n$ $component_{1}$ \text{component}_1 $component_{2}$ \text{component}_2 ... $component_{n}$ \text{component}_n $s l$ $s n$ $d l$ $d n$

$n$ - це додатне ціле число, що вказує на кількість карт. $component_{i}$ \text{component}_i описує $i$ -ту карту у наступному форматі.

$A$ $x_{1}$ x_1 $y_{1}$ y_1 $x_{2}$ x_2 $y_{2}$ y_2 ... $x_{A}$ x_A $y_{A}$ y_A $B$ $s_{1}$ s_1 $d_{1}$ d_1 $s_{2}$ s_2 $d_{2}$ d_2 ... $s_{B}$ s_B $d_{B}$ d_B $C$ $s n_{1}$ sn_1 $d l_{1}$ dl_1 $d n_{1}$ dn_1 $s n_{2}$ sn_2 $d l_{2}$ dl_2 $d n_{2}$ dn_2 ... $s n_{C}$ sn_C $d l_{C}$ dl_C $d n_{C}$ dn_C

$A$ позначає кількість вершин на карті. Кожен з наступних $A$ рядків містить два цілі числа $x_{i}$ x_i і $y_{i}$ y_i, що представляють координати $i$ -ї вершини на $2$ -вимірній площині. $B$ позначає кількість ребер, що з'єднують вершини на карті. Кожен з наступних $B$ рядків містить два цілі числа, що представляють початкову і кінцеву вершину кожного ребра. Вершини на одній карті нумеруються від $1$ .

$C$ позначає кількість варп-воротів. Кожен з наступних $C$ рядків має три цілі числа, що описують варп-ворота. Перше число - це вершина, де розташовані варп-ворота. Друге і третє число - це індекси карти і вершини, що представляють призначення варп-воротів. Аналогічно вершинам, карти також нумеруються від $1$ .

Після опису всіх карт слідують два рядки. Перший рядок містить два цілі числа $s l$ і $d l$ , що означають, що вхід у підземелля знаходиться на $s l$ -й карті, у вершині $d l$ . Останній рядок має два цілі числа $s n$ і $d n$ , аналогічно описуючи місцезнаходження виходу.

Значення в кожному наборі даних задовольняють наступні умови:

$1 \leq n \leq 50$ 1 \le n \le 50,
$3 \leq A \leq 20$ 3 \le A \le 20,
$A - 1 \leq B \leq A (A - 1) /2$ A-1 \le B \le A(A-1)/2,
$0 \leq C \leq A$ 0 \le C \le A, і
$- 10000 \leq x_{i}, y_{i} \leq 10000$ -10000 \le x_i, y_i \le 10000.

Вихідні дані

Для кожного набору даних виведіть відстань найкоротшого шляху від входу до виходу. Вихід не повинен містити абсолютну похибку більше ніж $1 0^{- 1}$ 10^{-1}. Якщо маршруту немає, виведіть $- 1$ .

Приклади

Приклад 1