AKBAR - Akbar , The great

All of us are familiar with the reign of the great mughal ruler, Akbar. He was always concerned with the prosperity and safety of the people. Therefore to safeguard his kingdom (which consisted of N cities) he wanted to place secret soldiers all over his kingdom so as to protect the people. But since his kingdom is very large therefore he wanted to place them in such a way that every city is protected by one and only one soldier.According to Akbar, this is the optimum placement.

As for these soldiers they can protect multiple cities according to their strengths.

The strength of a particular soldier is defined as the maximum distance upto which a guard can protect a city from its base city(base city is the city assigned to the guard). If there are 3 cities C1, C2 and C3 such that C1 C2 and C2 C3 are connected respectively, if a soldier with strength 1 is placed at C2 then all the cities C1, C2 and C3 are protected by that soldier.

Also the kingdom is connected with a network of secret two way roads for faster access only accessible to these soldiers. The length of any road on this network between any two cities is 1 kms. There are R such roads in the kingdom. 

He had given this task to birbal to place the soldiers. Birbal didn't wanted to be a fool in front of the king, therefore took the job and placed M soldiers all over the kingdom but he was not very good at mathematics. But since he is very intelligent he somehow places the guards all over the kingdom and now turns to you (who is a genius mathematician ;) ) to check whether his placements are good or not.

Your task is to check if the placements of the soldiers are optimum or not.

INPUT

The input consists of T test cases. Each test case then consists of 3 parts.The first line consists of N, R and M.

the next R lines consists of two numbers A and B denoting the two cities between which a road exists.

the next M lines consists of 2 numbers, city number K and strength S of that particular soldier.

=> strength 0 means it will only guard the city on which it is present.

=> assume every city is accesible from every other city.

CONSTRAINTS

T <= 10;

1 <= N <= 10^6;

N - 1 <= R <= min(10^7, (N * (N - 1) ) / 2));

1 <= K <= N;

0 <= S <= 10^6

OUTPUT

print "Yes" if the soldiers are placed optimally else print "No", (quotes are for clarity.)

SAMPLE

INPUT
2
3 2 2
1 2
2 3
1 2
2 0
4 5 2
1 4
1 2
1 3
4 2
3 4
2 1
3 0

OUTPUT
No
Yes

WARNING ==> Large input.


Added by:Prayank Mathur
Date:2014-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2019-02-06 16:07:20
@manoj_0786 I think you have to follow Birbal's order sequentially, and, it's not necessary for a soldier to look after every city under his strength. What's necessary here is to see if all the cities here are being protected by sequentially placing the soldiers at mentioned cities.
2018-11-29 07:11:23
ans must be no for this test case:
1
4 4 2
1 2
2 4
4 3
1 3
1 0
3 2

but they are giving yes
2018-09-18 06:03:59
Those having problem in first TC, read the words written in bold in problem statement
2018-07-07 22:38:24
use bfs
it can't be solved using dfs.
dry run this test case and you will get why dfs is not possible
1
4 4 1
1 2
1 3
2 3
3 4
1 2
2018-07-03 16:13:30
multipoint bfs
2018-07-01 20:12:28
Can we use DFS to solve the question ?
If anyone has tried can he/she send me his code . I am facing trouble in finding where my solution is getting wrong usinng DFS
Email ID : shivi98g@gmail.com

Your help will be surely appreciated
2018-06-20 14:15:14
good problem.loved it
2018-05-20 09:14:09
in sample test case they have given No as an ans for the first test case.
in city 1 soldier with strength 2 is present.
so he should be able to protect city 2 & 3 also.
so why is the answer no.
2018-03-18 22:58:18
Surprised to see this problem giving others so much grief. Passed in PyPy in 0.54s so TLE shouldn't ever be a worry for a C coder here. Now how the stats amassed 1736s WA's in 3200 submissions is beyond my comprehension. The logic is beautifully simple to represent without any corner-case handling.

Good problem with good constraints, had fun solving.
2018-01-29 12:58:07
fellas!, make sure you guys are printing "Yes" and not "YES", took me 3 WA to realise.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.