All Tracks Algorithms Graphs Depth First Search Problem

Maximal Connection.
Tag(s):

Medium-Hard, approved

Problem
Editorial
Analytics

Berland is a fantastic country, and all its cities are beautiful indeed. However, some of these cities are rather special, and have an amazing aura about them.

Overall, Berland consists of exactly $$N$$ cities enumerated using integers from $$1$$ to $$N$$, and $$M$$ of them are considered to be special $$( M \le N ) $$. These cities are connected by $$X$$ bi-directional roads, where the $$i^{th}$$ roads connectes two distinct cities $$u$$ and $$v$$.

Now, we call the Connection Power of city to be the number of special cities that are reachable from it. We say that city $$A$$ is reachable from city $$B$$, if by starting from city $$B$$ and traversing some sequence of roads in Berland, we can reach city $$A$$.

Now, you being a fantastically smart person, have been given the task of finding the summation of the Connection Powers of all $$N$$ cities.

Can you do it ?

Input Format :

The first line contains $$3$$ space separated integers $$N$$, $$M$$ and $$X$$, denoting the number of cities, number of special cities and the number of roads in Berland.

The next line contains $$M$$ space separated integers, denoting the indexes of the special cities.

Each of the next $$X$$ lines contains $$2$$ space separated integers $$u$$ and $$v$$, denoting an undirected road between city $$u$$ and $$v$$,

Output Format :

Print a single integer denoting the answer to the problem.

Constraints :

$$ 1 \le M \le N \le 10^5 $$

$$ 1 \le X \le 10^5 $$

$$ 1 \le u,v \le N $$

$$ u \ne v $$

SAMPLE INPUT
4 3 2
1 3 4
1 2
2 3
SAMPLE OUTPUT
7
Explanation

Cities $$1$$, $$2$$ and $$3$$ have a connection power equal to $$2$$ where-as city $$4$$ has a connection power equal to $$1$$.

So, the summation of these is equal to $$ 2 + 2 + 2 + 1 =7 $$

Time Limit: 1.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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

BuyHatke

Challenge Name

Buyhatke Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications