All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Owl Fight

Disjoint Set


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.

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.

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 \(TIE\).

1 \(≤\) N,M,Q \(≤\) \(10\)5
u,v \(≤\) N

Problem Setter - Harsh Jain

7 3
1 2
3 4
1 7
1 2
5 6
3 7
1 5

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications