Region of Calabria
Santa lives in the city of Calabria whose capital is Catanzaro. The city is beautiful and contains N different markets. You can consider the city as an undirected connected graph, in which the markets can be considered as nodes. Edge weights are 1. Now the problem with the Calabria is that K local dons are there and every don wants to rule the city. Thus after lots of wars they came to a conclusion that every don will be covering some radius from the node they are living at. A single market can't be shared by two dons. The position of dons are given, every don lives in one of the markets . Also, every don will cover equal radius. A radius of 'x' means that the particular don is covering all the markets(or nodes) with distance less than or equal to x from his position(the node he is residing in). But after the mutual understanding they decided to cover as many markets as possible. So given the graph, and the position of the dons in the city, you have to answer the maximum number of markets at which dons can cover up after the mutual understanding.
InputIn the first line there are 3 integers n,m,k denoting the number of markets, the number of roadways in the city and the total numbers of dons in the city respectively.
Next M lines contains the edge details , each line consists of two different numbers denoting the connections between markets.
Then in a separate line containing K distinct space-separated integers K1, K2, ..., denoting the position of the dons.
Output a single line denoting the maximum number of markets at which dons can cover up after the mutual understanding of covering equal radius.
- 2 ≤ N ≤ 100000
- N-1 ≤ M ≤ min( (N*(N-1))/2 ,100000)
- 1 ≤ K ≤ N
- 1 ≤ K[i] ≤ N
Input: 5 4 2 1 2 2 3 3 4 4 5 1 5 Output: 4
If radius is 1 then, markets 1 and 2 will be covered by don at market 1 and markets 4 and 5 will be covered by don at market 5.
If radius fixed is 2 then market number 3 will be covered by both at which dons will not agree.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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