P10734 [NOISG 2019 Prelim] Experimental Charges

Translated from [NOISG2019 Prelim C.Experimental Charges](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。

There are $N$ charged particles. A particle with a positive electron charge will attract a particle with a negative electron charge, while particles with the same electron charge will repel each other. There are $Q$ operations. Each operation is given as $T_i, A_i, B_i$, and can be one of three types depending on $T_i$: - Operation `A` means $A_i$ and $B_i$ attract each other. - Operation `R` means $A_i$ and $B_i$ repel each other. - Operation `Q` asks, based on the information known so far, what would happen if $A_i$ and $B_i$ are placed together. For each `Q` operation, if they attract each other, output `A`; if they repel each other, output `R`; if it cannot be determined, output `?`. It is guaranteed that there is at least one possibility such that all operations are consistent.

The first line contains two integers $N, Q$. The next $Q$ lines each contain a character $T_i$ and two integers $A_i, B_i$, describing an operation.

Output several lines, each line being the answer to one `Q` operation.

### Sample #1 Explanation For the first query, the relationship between $1$ and $2$ cannot be determined, so output `?`. For the second query, it can be determined that $1$ and $2$ repel each other, so output `R`. ### Constraints | $\text{Subtask}$ | Score | $N, Q$ | $T_i, A_i, B_i$ | | :----------: | :----------: | :----------: | :----------: | | $0$ | $7$ | $N = 2, Q \leq 10$ | None | | $1$ | $11$ | None | $A_i = 1$ or $B_i = 1$ | | $2$ | $14$ | None | $T_i$ can only be `R` or `Q` | | $3$ | $12$ | None | Queries only appear after all relationships are given | | $4$ | $25$ | $1 \leq N, Q \leq 10^3$ | None | | $5$ | $31$ | None | None | For $100\%$ of the testdata: - $1 \leq N, Q \leq 10^5$ - $1 \leq A_i \neq B_i \leq N$ - $T_i$ can only be `A`, `R`, or `Q`。 Translated by ChatGPT 5