Метро в Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии открылось метро. Жители рады новому виду транспорта, а особенно рад мэр города. Однако всегда есть что улучшить.

Метро представляет собой связный граф с $$$n$$$ вершинами и $$$n-1$$$ ребрами. Мэр хочет улучшить метро, делает он это с помощью приказов. Приказы бывают двух видов:

- $$$+$$$ $$$v$$$: Построить новую станцию и соединить ее со станцией $$$v$$$. Если номер последней построенной станции был $$$x$$$, то номер новой станции будет $$$x+1$$$
- $$$-$$$ $$$v$$$: Разрушить станцию $$$v$$$. Гарантируется, что после удаления этой станции, схема метро остается связной, то есть от любой станции можно добраться до любой другой.

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

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

Первая строка содержит число $$$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$$$ — построить новую станцию;
- - $$$v$$$ — разрушить станцию $$$v$$$.

Гарантируется, что $$$v$$$ это номер существующей на данный момент станции.

Гарантируется, что после каждой операции количество станций метро не меньше двух.

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

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

Пример

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

    51 21 51 43 16+ 5+ 6- 3+ 2- 7- 6

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

    7
    8
    6
    7
    6
    5