有 $N$ 棵由单个顶点构成的根树。顶点编号为 $1$ 到 $N$。
请编写一个程序执行以下查询：
1 u v：在 $u$ 和 $v$ 之间添加一条边。此时，$v$ 成为 $u$ 的父节点。保证在查询执行前，$u$ 是它所在树的根，并且 $u$ 和 $v$ 属于不同的树。2 v：删除连接 $v$ 和其父节点的边。$v$ 不是根节点。3 u v：输出 $u$ 和 $v$ 的最近公共祖先（LCA）。$u$ 和 $v$ 在同一棵树中。
输入格式
第一行包含两个整数 $N$ ($2 \le N \le 100{,}000$) 和查询数量 $M$ ($1 \le M \le 200{,}000$)。
接下来 $M$ 行，每行给出一个查询。
输出格式
对于每个类型为 3 的查询，按顺序每行输出一个结果。
样例
输入格式 1
5 9 3 1 1 1 1 2 1 3 2 1 4 3 3 1 4 3 3 4 2 4 1 5 3 3 1 5
输出格式 1
1 2 3 2