Задача №115367. Из Казани с любовью
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Марат — коренной казанец. Казань можно представить как неориентированное дерево, состоящее из \(n\) вершин. В молодости Марат нажил \(m\) врагов, пронумерованных от \(1\) до \(m\), живущих вместе с ним в Казани.
Каждый день все люди, живущие в городе, идут на работу. Марат знает, что \(i\)-й из его врагов живет в вершине \(a_i\) и работает в вершине \(b_i\). Сам он живет в вершине \(x\) и работает в вершине \(y\).
Все враги ходят на работу кратчайшим путем и выходят из дома в момент времени \(1\). То есть, если представить кратчайший путь между вершинами \(a_i\) и \(b_i\) как \(c_1, c_2, c_3, \ldots, c_k\), (где \(c_1 = a_i\) и \(c_k = b_i\)), то в момент времени \(p\) (\(1 \le p \le k\)) враг с номером \(i\) будет в вершине \(c_p\).
Марату очень не хочется встречаться в какой-то вершине в один момент времени со своими врагами, ведь это создаст неловкую ситуацию, при этом они могут встретиться на ребре . Марат также выходит из дома в момент времени \(1\), и в каждый следующий момент времени может либо переместиться в какую-то соседнюю вершину, либо остаться в текущей.
Помогите Марату найти минимальный момент времени, когда он сможет оказаться на работе, не встретившись по пути ни с одним врагом, или же определить, что это невозможно.
В первой строке входных данных дано четыре целых числа \(n, m, x, y\) (\(2 \le n \le 10^5\), \(1 \le m \le 100\), \(1 \le x, y \le n\), \(x \neq y\)) — количество вершин в дереве, количество врагов, а также номера вершин, откуда Марат начинает свой путь и куда он должен прийти, соответственно.
\(j\)-я из следующих \(n - 1\) строк содержит два целых числа \(v_j\) и \(u_j\) (\(1 \le v_j, u_j \le n\), \(v_j \neq u_j\)) — концы \(j\)-го ребра дерева.
\(i\)-я из следующих \(m\) строк содержит два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le n\), \(a_i \neq b_i\), \(a_i \ne x\)) — описание маршрутов врагов Марата.
Обратите внимание, что Марат может встретиться с \(i\)-м врагом только в моменты времени \(2, 3, \ldots, k\) (где \(c_1, c_2, \ldots, c_k\) — кратчайший путь между вершинами \(a_i\) и \(b_i\)). Другими словами, начиная с момента времени, следующего после того, как враг добрался на работу, Марат больше не может с ним встретиться . Также обратите внимание, что несколько врагов Марата могут находиться в одной и той же вершине в некоторые моменты времени.
Выведите одно целое число — минимальный момент времени, в который Марат сможет оказаться на работе, или \(-1\), если это невозможно.
Тесты к этой задаче состоят из примеров и \(5\) групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(m\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 15 | \(n \le 10\) | – | 0 | – |
| 2 | 15 | \(n \le 100\) | – | 0, 1 | – |
| 3 | 25 | \(n \le 3000\) | – | 0–2 | – |
| 4 | 15 | – | \(m = 1\) | – | – |
| 5 | 30 | – | – | 0–4 | – |
В первом примере можно дойти до вершины с номером \(4\) из вершины с номером \(1\) по кратчайшему пути. Обратите внимание, что Марат встретится с единственным врагом на ребре, а не на вершине.
Во втором примере оптимальная стратегия это подождать один момент времени в стартовой вершине и после этого пойти по кратчайшему пути от вершины \(1\) до вершины \(5\). Если не сделать остановку в начале, то Марат встретится со своим врагом в вершине, а не на ребре.
В третьем примере выгодно дойти из вершины \(1\) до вершины \(4\). После этого один момент времени никуда не двигаться, а после этого пойти по кратчайшему пути от вершины \(4\) до вершины \(9\).
4 1 1 4 1 2 2 3 3 4 4 1
4
5 1 1 5 1 2 2 3 3 4 4 5 5 1
6
9 2 1 9 1 2 2 3 3 4 3 5 5 6 6 7 6 8 8 9 9 1 7 1
10
9 2 1 9 1 4 2 5 3 6 4 5 5 6 4 7 5 8 6 9 2 8 3 7
6