Graph Queries Processing

This problem involves processing queries on an undirected graph. You are given a graph with n nodes and m edges. The graph is represented by a list of edges. You then need to answer q queries. There are two types of queries:

• Type 1: Given two nodes x and y, find the shortest path (measured by the number of edges) between them. If no path exists, output -1. Note that if x equals y, the shortest path length is 0.
• Type 2: Check whether nodes x and y are directly connected by an edge. Output yes if they are, and no otherwise.

The shortest path length can be formulated in LaTeX as follows:

$$ d(u,v)=\min\{\ell \mid \text{there is a path from } u \text{ to } v \text{ with } \ell \text{ edges}\} $$

Use an efficient Breadth-First Search (BFS) algorithm to handle type 1 queries.

inputFormat

The input is given via standard input (stdin) in the following format:

 n m
 u1 v1
 u2 v2
 ... (m lines of edges)
 q
 type1 x1 y1
 type2 x2 y2
 ... (q queries, each on its own line)

Where:

• n is the number of nodes (nodes are numbered from 1 to n).
• m is the number of edges.
• Each of the next m lines contains two integers u and v indicating an undirected edge between nodes u and v.
• q is the number of queries.
• Each query consists of three integers: the query type (1 for shortest path, 2 for direct connection), followed by two nodes x and y.

outputFormat

For each query, output the result on a separate line. For a type 1 query output the shortest path distance (or -1 if no path exists) and for a type 2 query output yes or no depending on whether the nodes are directly connected.

## sample

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

5
yes
3
no

</p>