U37082 星球大战

公元3145年，爆发了第二次宇宙大战。 有三个阵营，分别是猎犬座星系阵营，赛弗特星系阵营（不是赛博坦！），当然，还有我们的银河系阵营。 作为银河系阵营的总指挥，山不转水转决定先了解一下敌方阵地的详细信息。 对猎犬座星系阵营的侦查已经交给了少爷，现在你要负责的是对赛弗特星系阵营的侦查任务。 （出题人连夜赶工，所以题目背景与题目描述好像没有半毛钱关系，凑和着看吧。。。）

赛弗特星系有$n$个星球，一共$n-1$条虫洞连通这些星球。 我们不妨把这些星球编号为$1,2,3,...,n$。 这些星球均属于赛弗特星系阵营，所以有一个首都。 一开始首都为$1$。 但是这个首都是会变的！ 现在，他想知道，这些星球中某两个星球$x,y$之间虫洞连接的所有星球中，深度最小的那个星球。 深度的定义：$x$号星球的深度为$x$到首都经过的虫洞的数量$+1$。 简化版题意：给你一棵有根树，要求支持换根操作与求$LCA$操作。

第一行两个整数$n,m$，表示有$n$个星球，$m$个询问。 第2~n+1行，每行两个整数$x,y$，表示星球$x,y$之间有一条虫洞连接。 第n+2~m+n+1行，每行若干整数，描述如下： 1. 1 x 表示将首都换为$x$。 2. 2 x y 表示询问的两个星球的编号为$x,y$。

若干行，表示询问的答案。

10%：$n,m