Magical Portal Network

You are given a kingdom with n cities. Initially, no two cities are connected. However, magical portals can be added between cities so that one can travel between them, directly or indirectly. Your task is to process a series of queries and determine whether two given cities are connected by a sequence of portals.

There are three types of queries:

• ADDED P a b: Connects city a and city b by a portal. (Union operation in union–find)
• CONNECTED P a b: Checks if city a and city b are connected, either directly or via intermediate cities. Print YES if they are connected, otherwise NO.
• REMOVED P a b: This query is provided but should be ignored as removal of a connection is not supported in this problem.

Note: Cities are numbered from 1 to n. It is recommended to implement an efficient union–find (disjoint set) data structure with union by rank and path compression. Also, if any mathematical formula were to be included, use LaTeX formatting, e.g., if proving complexities use formulas like \(O(\alpha(n))\), where \(\alpha\) is the inverse Ackermann function.

inputFormat

Input: The input is read from stdin and begins with an integer T representing the number of test cases. For each test case:

1. A line containing two space‐separated integers n (the number of cities) and q (the number of queries).
2. q lines follow, each containing a query in one of the following formats: ADDED P a b, CONNECTED P a b, or REMOVED P a b.

Cities are numbered from 1.

outputFormat

Output: For each query of type CONNECTED, print a single line to stdout containing either YES or NO depending on whether the two cities are connected.

## sample

3
4 5
ADDED P 1 2
CONNECTED P 1 2
ADDED P 2 3
CONNECTED P 1 3
REMOVED P 1 2
4 3
ADDED P 1 4
ADDED P 2 3
CONNECTED P 1 3
3 1
CONNECTED P 1 3

YES
YES
NO
NO

</p>