Edge Resilience in Graphs

You are given an undirected graph with N nodes. The graph is initially empty and M edges are added sequentially. After adding some of the edges, there will be queries. Specifically, there are Q queries; in each query you are given two nodes u and v and you need to determine the minimum number of edges (taken from the beginning, in the given order) that have to be added so that u and v become edge-resilient. This means that in the resulting graph, for any single edge removal, u and v will still remain connected. Equivalently, there must exist at least two edge-disjoint paths between u and v (or, in other words, u and v are in the same 2-edge-connected component).

Note that if u and v are never connected even after adding all M edges, or if they remain vulnerable (i.e. there is always an edge whose removal disconnects them), then output -1 for that query.

Input Format: The input begins with three integers N, M, and Q on one line. The next M lines each contain two integers u and v representing an edge added to the graph (the edges are added in the given order). The next Q lines each contain two integers u and v representing a query.

Output Format: For each query, output one integer: the minimum number of edges required so that u and v become edge-resilient. If it is impossible, output -1.

Note: All formulas are in LaTeX format. For example, the requirement that there exist two edge-disjoint paths can be written as: $$ \text{There exist two edge-disjoint paths between } u \text{ and } v. $$

inputFormat

The first line contains three integers N, M, and Q representing the number of nodes, the number of edges, and the number of queries respectively.

The following M lines each contain two integers u and v (1-indexed) indicating that an undirected edge is added between nodes u and v. The edges are added in the given order.

The next Q lines each contain two integers u and v representing a query.

outputFormat

For each query, output a single integer on a new line. This integer is the minimum number of edges needed (from the beginning) such that the two given nodes become edge-resilient (i.e. removing any one edge does not disconnect them). If it is impossible, output -1.

sample

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

4