All Tracks Algorithms Graphs Depth First Search Problem

Arya's Stunt
Tag(s):

Easy

Problem
Editorial
Analytics

Arya Stark is now a trained assassin, and her aim is to destroy and kill Queen Cersei to avenge her father’s death. Being a trained assassin, Arya can easily sneak into enemy’s territory.

She uses this ability to enter the area where Cersei’s army is residing into their tents. There are ‘N’ number of tents in this area having ID 1,2,3..N . Some tents may be connected to each other via ropes. Arya wants to kill and injure as many warriors of Cersei’s army by burning the tents.

If there are ‘c’ no. of tents which are connected to each other via ropes, then Arya can light any one of these connected tents as warriors/soldiers of other ‘c-1’ tents will be alarmed by this activity. Suppose, Arya lights tent ‘X’ out of these c tents, then all the warriors of the tent ‘X’ will get killed and the warriors which are in the rest of the connected tents i.e. c-1 tents will get injured.

See sample explanation for more details.

Note –

  • If tent 1 is connected to tent 2, the tent 2 is also connected to tent 1.
  • If tent 1 is connected to tent 2 and tent 2 is connected to tent 3, then tent 1 is also connected with tent 3.

Now, Arya Stark wants to kill maximum no. of soldiers of Cersei’s army. Can you tell in advance how many soldiers will be killed and how many will get injured by this act of Arya Stark? Also output the number (ID) of tents which will be lighten by Arya. If more than one connected tents can be lighten then Arya will choose to light the tent whose ID will be minimum.

Input:

First line will contain two space separated integers N and M, i.e. the total number of tents and total number of connections between the tents.

Second line will contain ‘N’ space separated integers denoting the number of soldiers in i’th tent 1<=i<=N.

Next ‘M’ lines contains two spaced separated ‘a’ and ‘b’ denoting Tent ‘a’ and Tent ‘b’ are connected to each other via rope.

Output:

Two space separated integers denoting number of soldiers killed and number of soldiers injured respectively.

Next line contains the space separated ID of the lighten tents in increasing order of their ID’s.

Constraints:

  • 1<= N<= 10000
  • 1<= M<= 10000
  • 1<= No. of soldiers in each tent <=10000
SAMPLE INPUT
6 4
3 4 3 2 4 5
1 3
3 5
5 2
4 6
SAMPLE OUTPUT
9 12
2 6
Explanation

In the given case, there are 6 Tents numbered 1 to 6, which have 3,4,3,2,4,5 soldiers in respective tents.

Tents 1,2,3,5 are connected and Tents 4,6 are connected.

Arya will light tents numbered 2 and 6, lighting of tent 2 will result in killing of 4 soldiers in it and injuring soldiers of tents 1,3,5 and lighting of tent 6 will result in killing of 5 soldiers in it and injuring soldiers of tent 4. So, this will result in killing 9 soldiers and causing injury to 12 soldiers.

Time Limit: 0.5 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: Bash, 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, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ABV- Indian Institute of Information Technology and Management, Gwalior

Challenge Name

CodeMaze v3.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?