City and Soldiers

City and Soldiers

Today, King Trophies is on another rampage to destroy the small village controlled by Alex. Please help his soldiers.

At first, there are N individual soldiers, who haven't yet joined together; each of these soldiers is the leader of his/her own group. You have to handle 3 types of operations:

1) Two groups find each other, and the leader of the first group steps down.

2) A becomes leader of his group

3) Output the leader of a certain group

Input:

The first line contains the number N, the number of soldiers, and Q, the number of operations.

The next Q lines contains operations in the following format:

1 a b: Groups containing person a and person b find each other, and the leader of the group containing person asteps down, i.e., leader of group containing b becomes the leader of the merged group. If a is in b's group or vice versa ignore the operation.

2 a: a becomes the leader of his group.

3 a: Output the leader of the group containing person a.

Output:

Output the answer for each query of type 3.

Constraints:

1 <= N <= 10⁵

1 <= Q <= 10⁵

SAMPLE INPUT

2 2
1 1 2
3 1

SAMPLE OUTPUT

2

Explanation

Here, 2 will take over after 1 steps down.

--------------------------------------------------------------EDITORIAL-------------------------------------------------------

JUST  CHANGE THE REPRESENTATIVE OF THE  GROUP ....

---------------------------------------------------------CODE--------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli parent[1000000];
lli rankk[1000000];
lli find(lli a)
  {
    if(parent[a]!=parent[parent[a]])
     {
      parent[a]=find(parent[a]);
     }
     return parent[a];
 }

 int merge(int a,int b)
  {
  int pa=find(a);
  int pb=(find(b));
  parent[pb]=pa;
  rankk[pb]=0;
  //parent[a]=a;
  }
int main()
{
int n;
 cin>>n;
 int q;
  cin>>q;
  for(int i=0;i<=n;i++)
  {
  rankk[i]=1;
  parent[i]=i;
  }
  for(int i=0;i<q;i++)
  {
  int type ;
  cin>>type;
  if(type==1)
  {
  int a,b;
   cin>>a>>b;
  if(find(a)!=find(b))
       {
         merge(b,a);
   
 }
}
else if(type==2)
{
int a;
cin>>a;
int pa=find(a);
parent[pa]=a;
rankk[pa]=0;
parent[a]=a;
}
else
{
int a;
cin>>a;
// cout<<"call "<<endl;
cout<<find(a)<<endl;
// cout<<"call "<<endl;
}

  }
  return 0;
}