All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Mancunian And Nancy Play A Game
Tag(s):

Graph Theory, Medium

Problem
Editorial
Analytics

Mancunian is in a committed relationship with his girlfriend Nancy. His idea of a date is for them to have a romantic candlelight dinner and then play graph games. This time they are using a graph of $$N$$ nodes and $$E$$ edges. Mancunian is located at vertex $$M_1$$ and wants to move to $$M_2$$. Nancy wants to move from vertex $$N_1$$ to $$N_2$$. Anyone can move at any time, till both have reached their respective destinations. But there is a catch. Nancy can't bear to be too far away from her true love, Mancunian and hence the shortest distance between them at any point in time should never exceed a specified parameter $$K$$.

You are given several possible pairs of $$N_1$$, $$N_2$$ for Nancy. Count the number of such pairs which will make a valid game (where both Mancunian and Nancy can reach their respective destinations without violating the distance condition).

Input format

The first line contains three integers $$N$$, $$E$$ and $$K$$ denoting the number of vertices, number of edges in the graph and the maximum allowed distance between the two lovers respectively.
The following E lines contain two integers $$A$$ and $$B$$, denoting an undirected edge between those two vertices. There will be no self-loops or multiple edges in the graph.
Next line contains two integers $$M_1$$ and $$M_2$$ denoting the source and destination for Mancunian.
Next line contains a single integer $$Q$$ denoting the number of games.
Each of the next $$Q$$ lines contains two integers $$N_1$$ and $$N_2$$ denoting the source and destination for Nancy, for that game.

Output format

Print a single integer, denoting the number of valid games.

Constraints

  • $$1 \le N \le 100,000$$
  • $$1 \le E \le min(100,000, N*(N-1)/2)$$
  • $$1 \le K \le 1,000,000,000$$
  • $$1 \le Q \le 50,000$$
  • $$1 \le A, B, M_1, M_2, N_1, N_2 \le N$$
SAMPLE INPUT
6 5 3
1 3
2 3
3 4
4 5
3 6
1 5
1
2 6
SAMPLE OUTPUT
1
Explanation

The game may proceed in the following manner. Mancunian moves to vertex $$3$$ and then Nancy also moves to $$3$$. Mancunian moves to $$4$$, and then $$5$$. Nancy moves to vertex $$6$$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications