ООО «Логистика и маршруты» и ООО «Маршруты и логистика» — две конкурирующие компании. Они работают по стране, в которой N городов (все города пронумерованы от 1 до N), между какими-то парами городов проложены железнодорожные пути, при этом от любого города до любого можно добраться по последовательности этих путей единственным способом.

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

На протяжении Q лет произошло много изменений, ведь ровно тогда были основаны ООО «Логистика и маршруты» и ООО «Маршруты и логистика», и ровно тогда они начали привлекать клиентов. В один год могло произойти одно из пяти важных событий для этих компаний:

В следующем году на рынок хочет выйти новая компания ООО «Логистические маршруты и маршрутная логистика». Они наняли вас в роли аналитика и хотят восстановить историю двух конкурентов. Вы легко нашли всю информацию о контрактах, а вот расстояния вам придётся рассчитать самим.

В первой строке даётся целое число N — количество городов в стране (2 ≤ N ≤ 10⁵).

В следующих N−1 строках даются два целых числа u_i и v_i — номера городов, соединённые i-ми железнодорожными путями (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i). Гарантируется, что любую пару городов соединяет не более чем один железнодорожный путь.

В следующей строке даётся целое число Q — количество лет (3 ≤ Q ≤ 10⁵). В нулевой год у компаний не было заключено ни одного контракта.

В следующих Q строках описаны события в одном из 5 форматов:

Для каждого события выполняется неравенство 1 ≤ v ≤ N.

Для каждого года, когда контракты не менялись, выведите расстояние между логистическими сетями ООО «Логистика и маршруты» и ООО «Маршруты и логистика».