Shortest Path on a Cactus Graph

You are given a cactus graph with \(n\) vertices and \(m\) edges, and \(q\) queries. A cactus graph is an undirected graph in which every edge is contained in at most one simple cycle. There are no multiple edges between any pair of vertices. Each query consists of two vertices \(u\) and \(v\); your task is to compute the shortest path distance between these two vertices.

Input Format

The first line contains three integers \(n\), \(m\), and \(q\) separated by spaces.

The next \(m\) lines each contain two integers \(u\) and \(v\) representing an undirected edge between vertices \(u\) and \(v\).

The following \(q\) lines each contain two integers \(u\) and \(v\) for which you have to find the shortest distance between the two vertices.

Output Format

For each query, output a single integer representing the shortest path distance between \(u\) and \(v\) on a new line.

inputFormat

The first line of input contains three space-separated integers \(n\), \(m\), and \(q\).

The next \(m\) lines each contain two space-separated integers \(u\) and \(v\) indicating an edge between vertices \(u\) and \(v\).

The next \(q\) lines each contain two space-separated integers \(u\) and \(v\) representing a query asking for the shortest path from \(u\) to \(v\).

outputFormat

For each query, print one integer on a new line indicating the shortest path distance (i.e., the minimum number of edges) between the specified vertices \(u\) and \(v\).

sample

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

2
2