After a student started a rumour, you have been tasked with implementing a system to count the number of people that heard it for the 
~N~ students in the school: you will be asked 
~Q~ queries of 
~2~ types:
1 u v: 
~u~ and 
~v~ are now friends and can spread the rumour from their friends to each other.
2 x: If 
~x~ started a rumour, output the number of people that heard the rumour, including the starter.
Input Specification
The first line will contain ~N~ and ~Q~, the number of students and the number of queries.
The next ~Q~ lines will contain one of the above queries.
Output Specification
Output the answer to each type ~2~ query.
Constraints
For all subtasks:
~1 \le N, Q \le 100\,000~
~1 \le u, v, x \le N~
Subtask 1 [40%]
~1 \le N, Q \le 1\,000~
Subtask 2 [60%]
No additional constraints.
Sample Input
5 6
2 3
1 1 2
1 2 3
2 1
1 4 5
2 4
Sample Output
1
3
2
Explanation for Sample Output
For the 
~1^\text{st}~ query, the 
~3^\text{rd}~ student is only able to reach himself, so the answer is 
~1~. For the 
~2^\text{nd}~ query, the ~1^\text{st}~ student can reach himself and the ~2^\text{nd}~ and ~3^\text{rd}~ student. For the ~3^\text{rd}~ query, the 
~4^\text{th}~ person can only reach himself and the 
~5^\text{th}~ student.
Comments
My DFS TLEd on the 3rd batch :(
DFS will most likely TLE for this problem. Try using another data structure. You can also check the editorial for more tips.