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

Owl Fight
Tag(s):

Disjoint Set, Easy

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, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIIT Allahabad

Challenge Name

Codemania 2.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?