Почтальон Печкин после долгих лет исправной работы получил повышение и теперь возглавляет почтовую службу в городе $$$N$$$, состоящем из $$$n$$$ домов. Дома в этом городе соединены двусторонними дорогами от одного дома к другому, гарантируется, что от одного дома можно дойти по этим дорогам до любого другого. На его долю выпало модернизировать почтовую сеть города. Для начала ему необходимо построить распределительный склад в одном из домов города. Любая посылка будет сначала доставляться на склад, на котором она будет проверена службой безопасности, и только после этого отправлена получателю.
Печкин знает, что для того чтобы перенести посылку по дороге от одного дома к другому, почтальон зарабатывает одну единицу усталости. Так как Печкин уже не мало проработал в этой сфере, он хочет построить склад в таком доме, чтобы суммарная усталость почтальонов была минимальна. Под суммарной усталостью Печкин понимает сумму усталостей всех почтальонов при переносе всех посылок во всех направлениях (на склад и к получателю).
После проведения опроса жителей Печкин выяснил, какие планируются доставки на ближайший месяц, и, исходя из этих данных, собирается строить склад. Но Печкин — почтальон, поэтому он не справился с тем, чтобы вычислить, где ему будет лучше всего построить склад для выполнения его цели. Помогите Печкину, рассчитайте, где нужно расположить склад, зная, как устроены дороги в городе, и то, откуда и куда нужно будет доставлять посылки в ближайшее время.
В первой строке даны два числа $$$n, m$$$ — количество домов и дорог между ними в городе соответственно $$$(1 \le n \le 10^4, 0 \le m \le 10^5, n\cdot m \le 10^8)$$$
В следующих $$$m$$$ строках описаны дороги между домами, дорога существует между домами с номерами $$$a, b$$$ $$$(1 \le a, b \le n)$$$. Гарантируется, что между двумя домами может быть лишь одна прямая дорога, а так же что нет дорог из дома в него самого.
Далее дано число $$$k$$$ — количество посылок, которые необходимо перевезти Печкину. $$$(0 \le k \le 10^4)$$$.
В следующих $$$k$$$ строках надо по два числа $$$c,d$$$ — номера домов, из которого надо забрать посылку и в который её необходимо доставить.
Выведите одно число — ответ на задачу, номер дома, в котором выгоднее всего разместить склад.
Если подходящих ответов несколько, то разрешается вывести любой.
3 21 21 311 3
1
Рассмотрим пример из условия:
Если мы разместим склад в доме $$$1$$$, то посылка до склада переместится за $$$0$$$ единиц усталости, от склада до получателя за $$$1$$$ единицу усталости, итого за $$$1$$$ единицу усталости почтальон выполнит свою работу.
Если мы разместим склад в доме $$$2$$$, то посылка до склада переместится за $$$1$$$ е.у., от склада до получателя за $$$2$$$ е.у., итого за $$$3$$$ е.у. усталости почтальон выполнит свою работу.
Если мы разместим склад в доме $$$3$$$, то посылка до склада переместится за $$$1$$$ е.у., от склада до получателя за $$$0$$$ е.у., итого за $$$1$$$ е.у. почтальон выполнит свою работу.
Таким образом, нам подходят дома $$$1$$$ и $$$3$$$.
