Minimal Prefix Maximum Path Weight

You are given a connected undirected graph with n nodes and m edges. Note that the graph is not necessarily simple (it may have multiple edges between two nodes or self‐loops). The nodes are numbered from 1 to n.

We define the following concept on an integer sequence. For a sequence \(p_1, p_2, \dots, p_k\), we call \(p_i\) a prefix maximum if and only if there does not exist any index \(j\) with \(1 \le j < i\) such that \(p_j \ge p_i\). In other words, \(p_i\) is a prefix maximum if it is strictly greater than every element before it. The weight of the sequence is defined as the number of prefix maximums in it. Note that the first element \(p_1\) is always a prefix maximum because the condition holds vacuously.

You are given q queries. In each query, two nodes s and t are specified. Your task is to find a path \(p_1, p_2, \dots, p_k\) from s to t (i.e. \(p_1=s\) and \(p_k=t\)) such that, if we interpret the sequence of vertices on the path as an integer sequence, its weight is minimized. Note that the path is not required to be simple; you may traverse the same edge or node multiple times if needed. You only need to output the minimum weight.

Hint: When moving from a node \(u\) with current prefix maximum M to a neighbor \(v\), the new prefix maximum becomes \(\max(M, v)\). The cost increases by 1 only if \(v > M\), and remains the same if \(v \le M\). You can thus solve the problem using a modified shortest path algorithm (such as Dijkstra's algorithm) where each state is a pair (node, current\_max).

The formulas are given in \(\LaTeX\) format.

inputFormat

The first line of input contains three integers n, m, and q \((1 \le n \le N, \; 1 \le m \le M, \; 1 \le q \le Q)\) — the number of nodes, edges, and queries respectively.

Then follow m lines, each containing two integers \(u\) and \(v\) \((1 \le u, v \le n)\) representing an undirected edge between nodes \(u\) and \(v\). The graph is guaranteed to be connected.

After that, there are q lines; each line contains two integers s and t \((1 \le s, t \le n)\) representing a query asking for the minimal path weight from node s to node t.

outputFormat

For each query, output a single integer on a separate line — the minimal weight of a path from node s to node t.

sample

3 3 1
1 2
2 3
1 3
1 3

2