Find the cities
All submissions for this problem are available.
Rahul had recently won a prestigious prize, He was thus being called from n cities for giving lectures. The cities were connected (if at all) only by unidirectional roads.But Rahul was a miser. He would only prefer to travel by road as its the cheapest. Thus, he will go to a certain city by road, if and only if he can return by some road too.
Now Rahul needs your help. If he is present in a certain city, he wants to know the count of cities that he would not prefer to go.
First line will contain n (number of cities), m(number of roads), q(queries to be asked)
Next m lines contain pairs x and y denoting a road from city x to city y.
Next q lines contain the city number for which you need to give the answer.
For every city in queries print the number of cities he will not prefer to visit.
- 1 ≤ n ≤ 105
- 1 ≤ m ≤ 105
- 1 ≤ q ≤ 105
Input: 5 5 3 1 2 2 1 2 3 2 4 4 5 1 2 4 Output: 3 3 4
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.