题目描述
小L是某学校的一名学生,现在$6$年级,整个$6$年级共有$n$人。他们学校每过一段时间就会对班级进行一些操作,令小L很是头疼。经过一段时间的仔细观察,小L发现操作有$2$种:
- 将学生a所在的x班与b所在的y班合并,新班的班长会是y班的班长,表示为
1 a b
- 将学生a所在班的班长换成a,表示为
2 a
小L还发现一开始所有班都只有一人,也就是一开始有$n$个班,现在小L有些疑问,学生$a$所在班的班长是谁?表示为3 a
。小L发现自己会做这道题,但是他要准备应付期末考,就只好让请你来回答了,快帮帮他吧!
输入格式
$第一行输入两个整数n,m,表示有n名同学,共有m次操作与询问。$
$接下来m行,每行一个操作命令,如题所述。$
输出格式
对于每个询问,输出一个整数,占一行,表示班长是谁。
数据范围
$n,m<=100000$
输入数据
5 6
1 1 4
1 1 2
2 4
3 1
1 3 5
3 3
输出数据
4
5