疯狂科学家迈克构建了一棵有根树,由 n 个顶点组成。每个顶点都是一个水库,可以是空的,也可以是装满水的。
树的顶点从1到n编号,根在顶点1。对于每个顶点,其子节点的水库位于该顶点的水库下方,并且该顶点通过水可以向下流动的管道与每个子节点连接。
Mike 希望对树执行以下操作:
1. 用水填充顶点 v。然后 v 和它的所有子元素都充满了水。
2. 清空顶点 v。然后清空 v 及其所有祖先。
3、判断顶点v此时是否充满了水。
Mike 已经编制了他想要按顺序执行的操作的完整列表。在对树进行实验之前,迈克决定通过模拟运行该列表。帮助迈克确定执行所有操作后他会得到什么结果。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 500000) — 树中的顶点数。以下 n - 1 行中的每一行都包含两个以空格分隔的数字 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 树的边。
下一行包含数字 q (1 ≤ q ≤ 500000) — 要执行的操作数。以下 q 行中的每一行包含两个以空格分隔的数字 ci (1 ≤ ci ≤ 3)、vi (1 ≤ vi ≤ n),其中 ci 是操作类型(根据语句中给出的编号),vi 是执行操作的顶点。
保证给定的图是一棵树。
输出
对于每个类型 3 操作,如果顶点已满,则在单独的行上打印 1;如果顶点为空,则在单独的行上打印 0。按照输入中给出查询的顺序打印查询的答案。
示例
输入 #1
5 1 2 5 1 2 3 4 2 12 1 1 2 3 3 1 3 2 3 3 3 4 1 2 2 4 3 1 3 3 3 4 3 5
输出 #1
0 0 0 1 0 1 0 1