Graph Connectivity

You are given an undirected graph with n nodes and m edges. Your task is to answer k connectivity queries. In each query you are given two nodes a and b and you need to determine whether there exists a path between them.

The graph may be disconnected and can consist of several components. To solve this problem, it is recommended to use the Union-Find (or disjoint set union, DSU) data structure. In this problem, the union and find operations must be implemented with path compression and union by rank optimizations.

Note: All formulas are provided in LaTeX format. For example, the union operation decision is similar to comparing the ranks: \(\text{if } rank[u] > rank[v] \) then link \(v\) under \(u\).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n m
u1 v1
u2 v2
... (m edges)
k
a1 b1
a2 b2
... (k queries)

Where:

• T is the number of test cases.
• For each test case:
• n and m denote the number of nodes and edges respectively.
• The next m lines each contain two integers u and v, indicating an edge between nodes u and v.
• An integer k follows, representing the number of queries.
• The next k lines each contain a pair of integers a and b representing a query whether node a is connected to node b.

outputFormat

For each query in every test case, print YES on a new line if there is a path connecting the two nodes, otherwise print NO. The output is printed to standard output (stdout).

## sample

1
4 4
1 2
2 3
3 4
4 1
2
1 3
1 4

YES
YES

</p>