Experimental Charges
InterviewTime limit2sMemory limit512 MB
Particles carry unknown plus or minus charges; process attract/repel observations online and answer whether a queried pair must attract, must repel, or is unconstrained.
- Level
Medium5 of 10
- Topics
- Union-find, Graph, Implementation, Simulation
- Solved
- No attempts yet
Problem
There are N charged particles, each with either a positive or a negative charge. The charge on each particle is unknown, but it is known that if two particles with the same charge are brought close together, they repel each other, and if two particles with different charges are brought close together, they attract each other.
In an experiment, Q events happen in chronological order. Each event is one of the following two types:
- Two particles are brought close together, and you are told whether they repel or attract.
- You are asked whether two particles, when brought together, will repel, attract, or either is possible, based on the experimental observations so far.
It is guaranteed that at least one configuration of charges matches all the experimental observations given so far.
Input
Your program reads from standard input.
The input starts with a line with two integers, N and Q. N is the number of charged particles, and Q is the number of events.
Q lines follow, each with one character and two integers. The ith line contains Ti, Ai, and Bi. If Ti = ‘A’, it is a type 1 event where particles Ai and Bi attract. If Ti = ‘R’, it is a type 1 event where particles Ai and Bi repel. If Ti = ‘Q’, it is a type 2 event asking whether particles Ai and Bi attract or repel, or either is possible.
Output
Your program writes to standard output.
For every type 2 event, output one line with one character. Output ‘A’ if the charges attract, ‘R’ if they repel, or ‘?’ if either is possible.
Constraints
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai ≠ Bi ≤ N
- Ti = ‘A’, ‘R’, or ‘Q’