Power Game

0

0 votes
Graphs, Algorithms, Graph Representation
Problem

Sam and Andrea are playing a game today. On a paper, there is a connected graph drawn with N vertices and M edges. Every edge has a power assigned to it denoted by an array A[i].

In every turn, Sam & Andrea have to perform the following one by one:

  • Pick an edge which if removed will increase the number of connected components in graph.
  • Add the power of the edge picked above to the score.

If everyone played optimally, find the maximum & minimum score Sam can have if he start's the game first or second.

Input Format:

  • First line contains two space-separated integers N and M
  • Next line contains M space separated integers denoting the array A.
  • Next M lines containts two space-separated integers denoting an edge.

Output Format:

Print two space-separated integers denoting the maximum & minimum score Sam can have in the game.

Constraints:

1N,M1051A[i]106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Sam plays first

  • Sam picks edge 1-2 and Andrea picks edge 2-3.
  • Sam score is 10.

Sam plays second

  • Andrea picks edge 1-2 and Sam picks edge 2-3.
  • Sam score is 5.
Editor Image

?