Island Trip Connectivity

You are given a set of islands and a list of bidirectional bridges connecting pairs of islands. Two islands are considered connected if there exists a sequence of bridges that links them. Your task is to determine, for each query, whether there is a path connecting the two specified islands.

Input: The first line contains two integers representing the number of islands \(N\) and the number of bridges \(M\). The following \(M\) lines each contain two integers \(u\) and \(v\), indicating a bridge between island \(u\) and island \(v\). Next, a line containing an integer \(K\) is given, representing the number of queries. Each of the following \(K\) lines contains two integers \(a\) and \(b\) for which you must determine if a path exists between island \(a\) and island \(b\>.

Output: For each query, output a single line with "YES" if the two islands are connected, or "NO" if they are not.

This problem can be efficiently solved using either Depth-First Search (DFS) to identify connected components or the Union-Find (Disjoint Set) data structure.

inputFormat

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

The first line contains two integers (N) and (M): the number of islands and bridges respectively. Then follow (M) lines, each containing two integers (u) and (v) which indicate that there is a bridge between island (u) and island (v). The next line contains an integer (K) denoting the number of queries. Finally, (K) lines follow with each containing two integers (a) and (b); each query asks whether there is a path between island (a) and island (b).

outputFormat

For each query, print a single line to standard output (stdout) containing "YES" if there exists a path between the queried islands or "NO" if there is no such path.## sample

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

YES
YES
YES