All Tracks Algorithms Graphs Depth First Search Problem

Maximal Connection.

Medium-Hard, approved


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 \)

4 3 2
1 3 4
1 2
2 3

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


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Buyhatke Hiring Challenge

View All Notifications