В Берляндии открылось метро. Жители рады новому виду транспорта, а особенно рад мэр города. Однако всегда есть что улучшить.
Метро представляет собой связный граф с $$$n$$$ вершинами и $$$n-1$$$ ребрами. Мэр хочет улучшить метро, делает он это с помощью приказов. Приказы бывают двух видов:
Мэру города после каждого своего приказа интересно, за какое минимальное количество минут можно посетить все станции хотя бы один раз. Свой путь можно начинать с любой станции, а время перемещения между двумя соединенными станциями составляет ровно одну минуту.
Первая строка содержит число $$$n$$$($$$2 \leq n \leq 10^5$$$) — количество станций метро в изначальной схеме.
Далее идут $$$n-1$$$ строк. В $$$i$$$-й строке содержатся два числа $$$u_i$$$ и $$$v_i$$$($$$1 \leq u, v \leq 10^5$$$) — номера соединённых станций.
На следующей строке дано число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) - количество приказов мэра.
В следующих $$$q$$$ строках даются описания приказов в следующем виде:
Гарантируется, что $$$v$$$ это номер существующей на данный момент станции.
Гарантируется, что после каждой операции количество станций метро не меньше двух.
После каждого приказа выведите минимальное количество минут, за которое можно посетить все станции хотя бы один раз.
51 21 51 43 16+ 5+ 6- 3+ 2- 7- 6
7 8 6 7 6 5
