Owl Arena is hosting a fight competition and many owls decided to take part in it.

Strength of an owl is the number associated with that owl.

Rules of the competition are:

- An owl wins if its strength is greater than that of another.
- An owl can ask his friend to fight that match for him.

Note : If A and B are friends, and B and C are friends, then A and C are also friends.

Input:

First line contains the number of owls participating *N* and the number of connections *M*.*M* lines follow.

Each line contains two integers *u* and *v* denoting that they are friends.

Next line contains *Q*, the number of queries.*Q* lines follow.

Each line contains two integers *u* and *v*. You need to tell who wins.

Output:

In each query, output the number of the owl that will win the match. If the owls(*u* and *v*) are in the same friend circle, output .

Constraints:*1* *N*,*M*,*Q* ^{5}*u*,*v* *N*

Problem Setter

Explanation

1,2 and 7 are friends. 3 and 4 are friends. 5,6 and 7 have no friends. now,

First query: 1 and 2 : since both belong to the same friend circle, answer is a TIE.

Second: 5 and 6: since there is no friend of 5 and no friend of 6 and 6 has higher strength. 6 will win.

Third: 3 and 7: 3 has a friend 4 who has more strength than 3 and 7 has no friends whose strength is greater than his. so 4 vs 7. 7 will win.

Fourth: 1 and 5: 1 has a friend 7 who has more strength than 1 and 5 has no friends. so 5 vs 7. 7 will win. And since the fight was b/w 1 and 5. 1 wins the fight.

**Implementation code for above problem:**

#include<iostream>

using namespace std;

//For parent array

int a[100001];

int find(int f){

//if it is a parent

if(a[f]<0){

return f;

}

else{

return a[f]=find(a[f]);

}

}

void Union(int a1,int b1){

//assign element with larger value as parent to another

a[a1]=min(a[a1],a[b1]);

a[b1]=a1;

}

int main(){

int n,k;

cin>>n>>k;

for(int i=1;i<=n;i++){

a[i]=-i;

}

int a1,b1;

for(int i=1;i<=k;i++){

cin>>a1>>b1;

int para=find(a1);

int parb=find(b1);

if(para!=parb){

Union(para,parb);

}

}

cin>>k;

for(int i=1;i<=k;i++){

cin>>a1>>b1;

int para=find(a1);

int parb=find(b1);

if(para==parb){

cout<<"TIE"<<endl;

}

else if(a[para]<a[parb]){

cout<<a1<<endl;

}

else{

cout<<b1<<endl;

}

}

}

---------------------------------------------------

Input:

7 3

1 2

3 4

1 7

4

1 2

5 6

3 7

1 5

Output:

TIE

6

7

1

## Comments