Альпійська долина#9621

Альпійська долина

2 секунди

128 мегабайтів

Середня

В альпійській долині розташовано $n$ сіл (пронумерованих від $1$ до $n$ ), з'єднаних між собою $n - 1$ n - 1 дорогами. Хоча з будь-якого села можна дістатися до іншого, це може зайняти багато часу. Це особливо незручно, коли потрібно купити товари першої необхідності, адже магазини є лише в $s$ з $n$ сіл.

Цієї зими ситуація ускладнилася через сильний снігопад. Тому було б доцільно або залишити долину, діставшись до єдиного села $e$ біля гірського перевалу, що з'єднує долину із зовнішнім світом, або, принаймні, запастися припасами на кілька місяців. Сьогодні вранці ви почули по радіо, що через сніг одна з $n - 1$ n - 1 доріг стала непридатною для використання, але не зрозуміли, яка саме.

Тепер ви хочете дізнатися, чи зможете ви та ваші друзі покинути долину, і якщо ні, то наскільки далеко кожен з вас повинен проїхати, щоб дістатися до села з магазином. Ви не знаєте, яка дорога заблокована, а ваші друзі живуть у різних селах долини. Напишіть програму, яка відповість на це питання для $q$ комбінацій сіл і заблокованої дороги.

Вхідні дані

Перший рядок містить цілі числа $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5), $s$ , $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5) і $e$ , де $n$ - кількість сіл, $s$ ( $1 \leq s \leq n$ 1 \le s \le n) - кількість магазинів, $q$ - кількість запитів до вашої програми, а $e$ ( $1 \leq e \leq n$ 1 \le e \le n) - село, яке потрібно досягти, щоб залишити долину.

Кожен з наступних $n - 1$ n - 1 рядків містить три цілі числа $a$ , $b$ і $w$ . Вони означають, що дорога довжиною $w$ ( $1 \leq w \leq 1 0^{9}$ 1 \le w \le 10^9) з'єднує села $a$ і $b$ ( $1 \leq a \leq n$ 1 \le a \le n, $1 \leq b \leq n$ 1 \le b \le n).

Далі йдуть $s$ рядків: кожен містить одне ціле число $c$ , що означає, що в селі $c$ ( $1 \leq c \leq n$ 1 \le c \le n) є магазин. Всі ці рядки різні, тобто жодне село не містить більше одного магазину.

Нарешті, кожен з $q$ наступних рядків містить два цілі числа $i$ і $r$ , що означають, що $i$ -а дорога ( $1 \leq i < n$ 1 \le i < n, пронумеровані в порядку їх перерахування) вже не активна, а ви хочете дізнатися, чи зможуть ваші друзі, які проживають у селі $r$ ( $1 \leq r \leq n$ 1 \le r \le n), залишити долину, і якщо ні, то наскільки далеко знаходиться найближче село з магазином.

Вихідні дані

Виведіть $q$ рядків. $i$ -й рядок повинен містити відповідь на $i$ -й запит. Відповідний рядок повинен містити слово "escaped" (без лапок), якщо є можливість залишити долину; якщо ні, то рядок повинен містити відстань до найближчого села з магазином або слово "oo", якщо досягти магазину неможливо.

Приклади

Приклад 1

Приклад 2

Примітка

На рисунку показана ситуація до того, як дорога стала непридатною для використання. Села з магазинами позначені сірим кольором. Дороги позначені як "індекс / довжина". Вихід з долини знаходиться в селі $1$ .