Light OJ 1041 - Road Construction

Problem link -  1041 - Road Construction

In this problem we are given m roads with this roads we have to create a mst. If there are n cities and if we can select n-1 edges from  all edges when running mst then we can say we have a solution as we got a tree :-)

For mapping the cities we can use STL map.

let us try to analyze some test cases

2

Rajshahi Khulna 4

Kushtia Bhola 1

here we can't select (4-1)=3 edges when running mst so the output should be impossible.