Chukjibeop

A is troubled by severe traffic jams during the morning commute. A's area of activity has $N$ locations numbered $1$ through $N$ and $M$ two-way roads, each connecting two different locations. Crossing each road takes $1$ minute.

A, a skilled Taoist sorcerer, can use chukjibeop to move from any location to any other location in $1$ minute. However, teleporting from the current location to a location reachable by traveling along $0$ or more roads is considered cutting in line, which the sorcerers' code of ethics strictly prohibits.

Given $Q$ pairs of start and destination, find the minimum time to travel from the start to the destination for each pair.

The first line contains the number of locations $N$, the number of roads $M$, and the number of queries $Q$, separated by spaces. ($2 \le N \le 10^9$; $1 \le M \le 2\,000$; $1 \le Q \le 5 \times 10^5$)

Each of the next $M$ lines contains two integers $u$ and $v$, the endpoints of a road, separated by a space. ($1 \le u \lt v \le N$) No two roads have the same pair of endpoints.

Each of the next $Q$ lines contains a start $s$ and a destination $e$, separated by a space. ($1 \le s, e \le N$)

For each pair, print the minimum time to travel from the start to the destination on its own line, for $Q$ lines in total.