P1249 -- 水果堆

时间限制：1000MS

内存限制：131072KB

Description

grh神犇是个非常牛B的人，他看到前几周zgg的ACM赛里面的题目“抄写程序”，立马知道是合并果子，觉得太没难度，就想自己来合并果子。

于是，他随手从书包中掏出了凤梨，火龙果，杨桃，荔枝，西红柿，汤圆（汤圆也是水果？）等等N个水果…他给每个水果都标上了序号，从1到N。

有时候他会把标号为Q,P的水果所在的水果堆合成到一起，成为一堆。（尽管它们可能已经在同一堆里了），有的时候他因为太强，又忘了自己做过什么，于是他就想知道，标号为Q,P的水果是不是在同一堆里。

Input Format

输入第一行是两个整数N,M（1 <= N,M <= 200000），N表示有多少个水果，M表示他做了多少事。

接下来的M行中，每行包含三个整数T,Q,P，如果T=1，那么表示他把标号为Q和P的水果合成一堆。如果T=2，那么他表示想知道，标号为Q和P的水果是否在同一堆。

Output Format

输出包括若干行。输入每出现一个T=2的操作，输入一行。如果Q和P在同一堆，那么输出same，否则输出diff。

Sample Input

4 52 1 31 1 32 1 31 3 42 1 4

Sample Output

diffsamesame

Hint

对于20％的数据，保证有n,m<=100；

对于30％的数据，保证有n,m<=1000；

对于全部的数据，保证有n,m<=200000。

 

【题解】就是很裸的并查集的题目啊。。。

博主太懒不想写代码了