Заданы два дерева, на каждом стоит своя фишка. За один ход можно переместить обе фишки по своим деревьям на одно и то же расстояние (считается по числу рёбер в простом пути между стартовой и конечной вершинами). Требуется переместить пару фишек из заданной стартовой пары положений в конечную за минимальное число ходов.
В первой строке записаны числа $$$n_1$$$ ($$$1 \leq n_1 \leq 200\,000$$$), $$$n_2$$$ ($$$1 \leq n_2 \leq 200\,000$$$), $$$m$$$ ($$$1 \leq m \leq 200\,000$$$) — количество вершин в первом дереве, количество вершин во втором дереве и количество запросов. В следующих $$$n_1 - 1$$$ строках записаны пары чисел $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n_1$$$, $$$x_i \neq y_i$$$) — рёбра первого дерева. В следующих $$$n_2 - 1$$$ строках записаны пары чисел $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n_2$$$, $$$x_i \neq y_i$$$) — рёбра второго дерева. В следующих $$$m$$$ строках записаны запросы. Каждый запрос — это четвёрка чисел $$$s_1$$$ ($$$1 \leq s_1 \leq n_1$$$), $$$s_2$$$ ($$$1 \leq s_2 \leq n_2$$$), $$$t_1$$$ ($$$1 \leq t_1 \leq n_1$$$), $$$t_2$$$ ($$$1 \leq t_2 \leq n_2$$$) — стартовая позиция первой фишки на первом дереве, стартовая позиция второй фишки на втором дереве, финишная позиция первой фишки на первом дереве, финишная позиция второй фишки на втором дереве соответственно.
На каждый из $$$m$$$ запросов выведите по одному числу — минимальное количество ходов, необходимое, чтобы добраться из стартовой пары позиций в конечную. Если добраться невозможно, выведите в соответствующей строчке -1.
4 5 7 1 2 2 3 2 4 1 2 2 3 3 4 4 5 1 1 2 5 1 5 4 1 1 5 4 2 2 5 2 3 2 1 2 5 3 2 3 2 4 4 1 2
-1 2 -1 2 3 0 1
| 2021-2022 ICPC, Moscow Subregional |
|---|
| Закончено |
