29077번 - Захват провинций 다국어

Дэдпул решил поквитаться с канадским правительством. Одному ему будет справиться непросто, поэтому он решил осуществить свой план вместе с неподражаемой Копикэт.

Дэдпул решил захватить всю Канаду. А потом отпустить, забавы ради. Канада разбита на несколько административных единиц, для простоты будем называть их провинциями. Некоторые провинции соединены двунаправленными дорогами. Всего в Канаде $n$ провинций и $n-1$ дорога. Между любыми двумя провинциями существует единственный простой путь. Иными словами, Канада представляет собой дерево.

В ходе выполнения плана Дэдпул захватывает некоторые провинции, а некоторые --- освобождает. После каждого действия Дэдпула под его контролем оказываются провинции, принадлежащие минимальному связанному подграфу, который содержит все захваченные провинции. Обратите внимание, что каждая захваченная провинция находится под контролем Дэдпула, но не каждая провинция под его контролем является захваченной.

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

От вас требуется для каждой поездки определить, сколько подконтрольных Дэдпулу провинций встретится на пути ее следования.

Изначально все провинции свободны.

Если одна или обе конечные провинции поездки находятся под контролем Дэдпула, то они так же учитываются при подсчете.

В первой строке находится одно натуральное число $n$ ($1 \le n \le 10^5$) --- количество провинций.

В каждой из следующих $n-1$ строке находятся два натуральных числа $u$, $v$ ($1 \le u, v \le n, u \neq v$) --- номера провинций, соединеных двунаправленными дорогами. Гарантируется, что заданный граф является деревом.

В следующей строке находится натуральное число $m$ ($1 \le m \le 10^5$) --- количество событий. В каждой из следующих $m$ строк заданы события в хронологическом порядке, в следующем формате: сначала идет натуральное число $t$ ($1 \le t \le 2$) --- тип запроса,

• если $t = 1$, то далее следует одно натуральное число $x$ ($1 \le x \le n$) --- номер провинции, с которой производит действие Дэдпул: захватывает, если до этого провинция была свободна, и освобождает, если до этого провинция была захвачена;
• если $t = 2$, то далее следуют два натуральных числа $x$, $y$ ($1 \le x, y \le n$) --- номера провинций, между которыми совершается поездка.

Для каждой поездки выведите, сколько подконтрольных Дэдпулу провинций встретится на пути ее следования.