AOE NIGHT AT IITG

0

0 votes
Problem

A group of N friends have decided to play Age Of Empires on LAN tonight. Naturally some of them have formed alliances and some have declared war on some others. Being an awesome programmer and hacker you have decided to exploit these relationships by writing a program to generate a strategy to help you win. Your program receives information about alliances and wars. To develop a strategy you need to quickly know whether given two players A and B, are friends, enemies or neutral. Rules of friend/enemy relationships are given below.

  1. A is friend of B => B is friend of A. Similarly, A is an enemy of B => B is an enemy of A.

  2. A is a friend of B and B is a friend of C => A is a friend of C.

  3. A is an enemy of B and B is an enemy of C => A is a friend of C.

  4. A is an enemy of B and B is friend of C => A is an enemy of C.

  5. A is friend of B and B is an enemy of C => A is an enemy of C.

You will receive Q queries. Some will define a relationship between two players. And others will ask you the relationship between given two players. You are required to give an answer to each query as explained below.

NOTE: Friends are numbered from 0 to (N-1).

INPUT:

First line contains T, the number of test cases.

First line of each test case contains N and Q. N denotes the number of players in the game and Q denotes the number of queries.

Each of the following Q lines are of the form:

"0 X Y" or "1 X Y" or "2 X Y"

"0 X Y": You have received information that X and Y are friends.

"1 X Y": You have received information that X and Y are enemies.

"2 X Y": Answer whether X and Y are friends/enemies/neutral.

OUTPUT:

For queries of form "0 X Y" and "1 X Y" print on a new line "OK" if the currently recieved information creates no conflicts with previous information, or "CONFLICT" if the received information creates conflicts with previous information. (If there is a conflict, discard the currently received information.)

For queries of form "2 X Y" print "FRIENDS" or "ENEMIES" depending on the present alliance status of X and Y. If no inference can be made based on known information, print "NEUTRAL".

CONSTRAINTS:

1<=T<=10

1<N<20000

1<Q<100000

PROBLEM SETTER: Shreyas Basarge

Time Limit: 4
Memory Limit: 256
Source Limit:
Editor Image

?