Shortest Path Queries in an Undirected Graph

You are given an undirected graph with n nodes (cities) and m edges connecting them. Then, you will be given q queries. Each query consists of two cities; your task is to determine the shortest path length between these two cities.

The graph is defined by its nodes and edges without any weights. Thus the shortest path between two nodes is the path that contains the minimum number of edges. Mathematically, for two nodes \( u \) and \( v \), the distance is defined as \( d(u,v)=\min\{\ell(P)\} \), where \( \ell(P) \) denotes the number of edges in path \( P \) connecting \( u \) and \( v \).

inputFormat

The input is given from stdin and has the following format:

• The first line contains three integers: n (the number of nodes), m (the number of edges), and q (the number of queries).
• The next m lines each contain two integers u and v, meaning there is an undirected edge between nodes u and v.
• The following q lines each contain two integers a and b, representing a query for the shortest path length between nodes a and b.

outputFormat

For each query, output a single line containing one integer which is the length of the shortest path from node a to node b on stdout.

## sample

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

3
2
1

</p>