Owl Fight
Tag(s):

## Disjoint Set

Problem
Editorial
Analytics

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 $TIE$.

Constraints:
1 $≤$ N,M,Q $≤$ $10$5
u,v $≤$ N

Problem Setter - Harsh Jain

SAMPLE INPUT
7 3
1 2
3 4
1 7
4
1 2
5 6
3 7
1 5
SAMPLE OUTPUT
TIE
6
7
1
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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Codemania 2.0

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Data Structures > Arrays
• Math > Number Theory
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Basic Programming > Input/Output
• Basic Programming > Implementation