Another Contest 1 Problem 2 - Graphs

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type

This problem has a simple statement.

Given an undirected, unweighted graph of N vertices and M edges, and Q pairs of vertices, compute the distance between each pair of vertices.

We ran out of time trying to set strong test data for the problem though, so we did it randomly. Here's how we generated our test data.

• We picked values for , , and . The vertices are numbered from to .
• We generated, uniformly at random, a pair of distinct integers between and and added an edge between those vertices as long as they weren't already directly connected by an edge. This means the graph has no self-loops, nor parallel edges.
• The above step was repeated until the graph contains exactly edges.
• We generated, uniformly at random, pairs of integers between and for the queries.

Constraints , , and .

Note: The sample does not respect the constraints. Your solution does not need to produce the correct output on the sample to get AC.

Input Specification

The first line of input contains three positive integers, , , and .

The next lines each contain two distinct positive integers from to , representing an edge between the two given vertices.

The next lines each contain two positive integers from to , representing a distance query between the two given vertices.

Output Specification

Output lines. For each distance query, output -1 if the two vertices are disconnected, otherwise output the distance between the two vertices. Output answers for the queries in the order they're given, one query per line.

3 2 2
1 2
2 3
1 3
2 3

2
1