Another Contest 1 Problem 2 - Graphs - DMOJ: Modern Online Judge

Another Contest 1 Problem 2 - Graphs

Points: 15

Time limit: 0.6s

Memory limit: 256M

Problem type

This problem has a simple statement.

Given an undirected, unweighted graph of $N$ ~N~ vertices and $M$ ~M~ edges, and $Q$ ~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 $N$ ~N~, $M$ ~M~, and $Q$ ~Q~. The vertices are numbered from $1$ ~1~ to $N$ ~N~.
We generated, uniformly at random, a pair of distinct integers between $1$ ~1~ and $N$ ~N~ 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 $M$ ~M~ edges.
We generated, uniformly at random, $Q$ ~Q~ pairs of integers between $1$ ~1~ and $N$ ~N~ for the queries.

Constraints

$N = 10^5$ ~N = 10^5~, $M = 2 \cdot 10^5$ ~M = 2 \cdot 10^5~, and $Q = 10^4$ ~Q = 10^4~.

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, $N$ ~N~, $M$ ~M~, and $Q$ ~Q~.

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

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

Output Specification

Output $Q$ ~Q~ 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.

Sample Input

Sample Output

2
1

Comments

0

349081547 commented on Sept. 14, 2019, 11:01 p.m. ← edited →

I literally just started c++. Is there something wrong with my program?? It says the compiler output is too long.

22

xiaowuc1 commented on Sept. 14, 2019, 11:13 p.m. ← edited →

Your code does not compile. You should compile your code on your machine before submitting it - if the compiler output is too long, that usually means you have too many compiler errors. If your code does compile, it will automatically be run on the test cases.

If you can't compile locally for some reason, you can use a service like ideone.com. If you click on the link in the previous sentence, you can see the compiler errors for your program. You should fix the first errors before looking at the later ones.

0

349081547 commented on Oct. 26, 2019, 2:13 p.m.

thanks!