树上博弈
题号：NC233098
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵 n 个点的树，定义一个两个人的博弈过程如下。

定义一个变量 x，初始值为 k，其中 k 是一个给定值，初始有一个石子，位置在 p。

两人轮流操作：

找到 z，满足 ，其中 dis(x,y) 表示两个点在树上的最短路径长度，若不存在这样的 z，则判负，然后令 。

你需要支持：

1. 在树上加入一个新的点。

2. 给定 k,p，判断是否先手必胜。

输入描述:

第一行两个正整数 。

之后 n-1 行，每行两个整数 x,y，表示树上一条 x,y 之间的双向边。

之后 q 行，每行形如  或 。

若第一个数为 1，令当前点数为 N，新建一个编号为  的点，并新建一条与 x 相连的边。

否则表示一次询问。

输出描述:

对于每一组询问，输出 1 表示存在必胜策略，否则输出 0 表示没有。
示例1

输入

复制 
5 4
1 2
1 3
1 4
2 5
1 2
2 3 3
2 2 3
2 0 6

输出

复制 
0
1
1

说明

对于第一个询问，先手没有可以第一步走出的点。

对于第二个询问，先手可以第一步走到点 6，此时后手无点可走。

备注:

保证  当前点数，且 k 为自然数。