410174: GYM103967 J Халат Рика

J. Халат Рикаограничение по времени на тест3 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рик решил постирать свой халат. Но у него не так много времени до очередного безумного приключения, поэтому вместо нормальной стирки он намочил $$$s$$$ точек халата специальным раствором и теперь ждет, когда халат высохнет.

Раствор, созданный Риком, обладает подобием разума, поэтому вместо того, чтобы неэффективно испаряться, растекается по халату. Сам же халат можно представить в виде неориентированного графа на $$$n$$$ вершинах и $$$m$$$ ребрах. Точки, которые Рик намочил раствором — это $$$k$$$ различных вершин графа. Также, как, наверное, можно было заметить, Халат Рика очень старый, поэтому в нем имеются $$$t$$$ дырок (еще $$$t$$$ различных вершин), и как раз через них раствор может стекать.

Рик точно не создал бы раствор, который действует не оптимально, ведь у него не так много времени, поэтому раствор из каждой изначальной точки течет до ближайшей дырки и весь через нее вытекает. На прохождение одного ребра ткани раствору требуется одна единица времени. По одному ребру одновременно может течь любой объем раствора. Рик посчитал, через какое время весь раствор вытечет из халата через дырки, и считает, что это слишком долго. Поэтому он хочет проделать в халате еще одну дырку в любой вершине, чтобы ускорить процесс. Помогите ему определить, какую вершину стоит продырявить, чтобы минимизировать время, за которое все капли раствора доберутся до ближайших дырок.

Раствор при этом работает моментально, поэтому после нанесения можно дырявить сразу дырки, в которых находится раствор, если это минимизирует ответ. Поскольку возможных выборов конечной вершины может быть несколько, Рик просит вас найти вершину с минимальным номером, при добавлении дырки в которой искомое расстояние минимизировано.

Входные данные

В первой строке через пробел даны целые числа $$$n$$$, $$$m$$$, $$$s$$$ и $$$t$$$ — количество вершин и ребер в халате, а также количество изначально намоченных точек и дырок, соответственно ($$$1 \leqslant n, m \leqslant 2 \cdot 10^5$$$; $$$1 \leqslant s \leqslant \min(n, 100)$$$; $$$1 \leqslant t \leqslant n$$$).

В следующей строке через пробел перечислены $$$k$$$ различных целых чисел $$$p_i$$$ — номера вершин, которые Рик намочил раствором ($$$1 \leqslant p_i \leqslant n$$$).

В следующей строке так же перечислены $$$t$$$ различных целых чисел $$$q_i$$$ — номера вершин, в которых в халате находятся дырки ($$$1 \leqslant q_i \leqslant n$$$).

Следующие $$$m$$$ строк содержат описание ребер графа. В $$$i$$$-й из них через пробел даны два целых числа $$$v_i$$$ и $$$u_i$$$, означающие, что в графе есть ребро между вершинами $$$u_i$$$ и $$$v_i$$$ ($$$1 \leqslant v_i, u_i \leqslant n$$$).

Выходные данные

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

Разрешается выводить номер вершины, которая уже является дыркой, если ни при каком выборе другой вершины ответ не улучшится. Если возможных ответов несколько, выведите тот из них, в котором номер выбранной вершины минимален (независимо от того, есть в ней уже дырка или нет).

ПримерВходные данные

7 6 4 1
4 5 6 7
1
1 2
2 3
3 4
4 5
3 6
6 7

Выходные данные

3 2