Description:


火车司机出秦川,跳蚤国王下江南,共价大爷游长沙。每个周末,勤劳的共价大爷都会开车游历长沙市。
长沙市的交通线路可以抽象成为一个 n 个点 n−1 条边的无向图,点编号为 1 到 n,任意两点间均存在恰好一条路径,显然两个点之间最多也只会有一条边相连。有一个包含一些点对 (x,y) 的可重集合S,共价大爷的旅行路线是这样确定的:每次他会选择 S 中的某一对点 (x,y),并从 x 出发沿着唯一路径到达 y。
小L是共价大爷的脑残粉,为了见到共价大爷的尊容,小L决定守在这张图的某条边上等待共价大爷的到来。为了保证一定能见到他,显然小L必须选择共价大爷一定会经过的边——也就是所有共价大爷可能选择的路径都经过的边。
现在小L想知道,如果他守在某一条边,是否一定能见到共价大爷。
然而长沙市总是不断的施工,也就是说,可能某个时刻某条边会断开,同时这个时刻一定也有某条新边会出现,且任意时刻图都满足任意两点间均存在恰好一条路径的条件。注意断开的边有可能和加入的新边连接着相同的两个端点。共价大爷的兴趣也会不断变化,所以S也会不断加入新点对或者删除原有的点对。当然,小L也有可能在任何时候向你提出守在某一条边是否一定能见到共价大爷的问题。你能回答小L的所有问题吗?

Input:


输入的第一行包含一个整数 id,表示测试数据编号,如第一组数据的id=1,样例数据的 id 可以忽略。hack数据中的 id必须为 0 到 10 之间的整数。hack数据中id的值和数据类型没有任何关系。
输入的第二行包含两个整数 n,m,分别表示图中的点数,以及接下来会发生的事件数,事件的定义下文中会有描述。初始时 S 为空。
接下来 n−1 行,每行两个正整数 x,y,表示点 x 和点 y 之间有一条无向边。
接下来 m 行,每行描述一个事件,每行的第一个数 type 表示事件的类型。
若type=1,那么接下来有四个正整数x,y,u,v,表示先删除连接点x和点y的无向边,保证存在这样的无向边,然后加入一条连接点u和点v的无向边,保证操作后的图仍然满足题中所述条件。
若type=2,那么接下来有两个正整数 x,y,表示在 S 中加入点对 (x,y)。
若type=3,那么接下来有一个正整数 x,表示删除第 x 个加入 S 中的点对,即在第 x 个 type=2 的事件中加入 S 中的点对,保证这个点对存在且仍然在 S 中。
若 type=4,那么接下来有两个正整数 x,y,表示小L询问守在连接点 x 和点 y 的边上是否一定能见到共价大爷,保证存在这样的无向边且此时 S 不为空。

Output:


对于每个小L的询问,输出“YES”或者“NO”(均不含引号)表示小L一定能或者不一定能见到共价大爷。

Sample Input:


Sample Output


Explanation:


最开始将点对 (1,5) 加入到 S 中,此时点 1 和点 5 之间的路径是 1→5。
接着将连接点 1 和点 5 的边断开,加入连接点 2 和点 5 的边,我们发现图仍然满足题中所述条件,且点 1 和点 5 之间的路径是 1→2→5,经过点了 2 和点 5 之间的边,因此第一个询问答案是 YES。
接着将点对 (1,4) 加入到 S 中,点 1 和点 4 之间的路径是 1→2→4,没有经过点 2 和点 5 之间的边,因此第二个询问答案是 NO。
接着,我们删除了第一个加入到 SS 中的点对,也就是点对 (1,5),此时 SS 中唯一的点对就是 (1,4),经过了点 2 和点 4 之间的边,因此最后一个询问答案是 YES。

题解:


毛爷爷的题,早就听说了,于是就来找虐。
毛爷爷的题,哪个我做出来过?(´゚д゚`)

于是开开心心做了50分看题解去了。嗯,这是一道动态树维护子树信息的好题。

50分做法:

由于2~5个数据没有1操作,所以直接用LCT维护,对于加入路径,把u到v的权值加上1,对于删除路径,把u到v的权值减去1。
对与询问,直接查询u, v的权值是否都为|S|。
再加上暴力,就可以拿到50分。
代码如下:(比正解还要长。。。)

100分做法:

参见毛爷爷博客《共价大爷游长沙》解题报告
注意在维护子树信息的做法我之前的access貌似是不行的,这里感谢LYQ的帮助。

代码如下:

不要问我随机种子是什么。
手动滑稽。