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 optimumly 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
SAMPLE OUTPUT
No
Yes
WARNING ==> Large input.
hide comments
saurav3199:
20191213 15:23:39
dont knoww what i am doing wrong my submission id is 25062209 

techmac:
20191104 05:38:31
use multiple bfs depending on where the soldier is placed.


akshadv48:
20191022 15:41:51
can any one please post the python code for this


itachi_2016:
20191013 20:14:12
It was fun! Question is not poorly worded. Read the statement carefully "every city" is protected by "one and only one" soldier. Also take care of TLE, you don't need to clear your visited array every time. Last edit: 20191013 20:14:46 

ankit_btech:
20190713 23:27:37
I don't see why people are saying the question is poorly worded. It is a pretty good question, and in fact a really good one to start with. 

manunem:
20190709 10:54:30
can someone please post the explanation to this problem and also the code. I'm a beginner 

sajalagrawal14:
20190622 12:22:39
good question , just take care that you are printing Yes not "YES" ...hahaha it cost me 5 wa 

aj_254:
20190421 14:29:43
just make sure that each is gaurded by any one number of gaurds ...if even one city left ungaurded print no


aj_254:
20190421 13:02:16
ac in pypi2 0.78 sec. after 4 tle and 9 wa.. very tricky question language is very bad,,in python use deque during bfs for ac Last edit: 20190421 13:02:38 

ashwani_er:
20190331 12:11:34
The problem statement is ambiguous. A city having no soldier should be protected by any no. of soldier and if a city has a soldier assigned to it then only that soldier should protect it.

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