Мексика — одна из самых интересных стран для путешественников. Бескрайние песчаные пляжи, самобытная культура, древние храмы индейцев, разнообразная природа — тропические леса, горы, пустыни и... конечно же, кактусы!

Путешественник прибыл в Мексику и решил досконально изучить страну. Для этого он взял в прокате машину и составил план посещения городов страны на K дней вперёд.

Известно, что в Мексике есть N городов и M дорог. Каждая дорога соединяет два различных города, и никакие две дороги не соединяют одинаковую пару городов. При этом все дороги имеют одинаковую длину и являются двусторонними, а из каждого города можно добраться по дорогам в любой другой.

Кроме того, если представить дорожную сеть Мексики в виде графа с вершинами в городах и ребрами-дорогами, то такой граф будет являться вершинным кактусом — связным неориентированным графом, в котором каждая вершина лежит не более чем на одном простом цикле.

Турист начинает своё путешествие по городам Мексики в городе 0. Согласно плану, каждый день турист выбирает город для осмотра и едет в него из города, в котором он был в предыдущий день по кратчайшему пути. Если город при этом не меняется, то турист совершает поездку по достопримечательностям в пределах города.

Каждый раз, когда турист куда-то едет, он должен заправить машину в городе, который находится ближе всего к середине его пути. Если таких городов существует несколько, то выбирается любой из них.

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