Room Connectivity Analysis

You are given one or more datasets representing a network of rooms connected by doors. Each door represents a bidirectional connection between two rooms. For each dataset, your task is to determine the shortest path (i.e. the minimum number of doors traversed) between a pair of rooms as specified by several queries.

This problem can be modeled as finding the shortest path in an unweighted, undirected graph using Breadth-First Search (BFS). For each query, if a path exists between the given starting room and target room, output the minimal number of doors (edges) required; otherwise, output NO.

The datasets are presented using the following format:

• The first line contains an integer T representing the number of datasets.
• For each dataset:
  • An integer R (informational: number of rooms).
  • An integer M indicating the number of direct connections.
  • The next M lines each contain two integers representing a connection (two rooms connected by a door).
  • An integer Q specifying the number of queries.
  • The next Q lines each contain two integers representing a query (the start and target rooms).

inputFormat

The input begins with an integer T, the number of datasets. For each dataset, the input is formatted as follows:

R
M
a1 b1
...
aM bM
Q
s1 t1
...
sQ tQ

Here, R is an informational integer representing the number of rooms, M is the number of connections, each connection is represented by two integers a and b (indicating a bidirectional door between room a and room b), Q is the number of queries, and each query consists of two integers s and t for the start and target room respectively.

outputFormat

For each dataset, output the answers for all queries in a single line where each answer is separated by a space. For each query, if a path exists from the start room to the target room, output the minimum number of doors that need to be traversed; otherwise, output NO.

## sample

2
5
5
1 2
2 3
3 4
4 5
1 5
2
1 5
2 4
3
3
5 6
6 7
7 8
4
5 6
6 8
5 7
7 9

1 2
1 2 2 NO

</p>