All Tracks Algorithms Graphs Minimum Spanning Tree Problem

Monk and Tree
Tag(s):

Ad-Hoc, Graph, Graph Theory, Medium, Minimum spanning tree

Problem
Editorial
Analytics

We all know that Monk is a competitive programmer. While participating in one of the contest, Monk encountered a graph theory problem. As graph theory being one of his weak links, he was unable to think any solution for the problem and has become sad. Can you help Monk and make him happy.

You are given an undirected graph consisting of N nodes. All the nodes have distinct numbering from 1 to N. There is at most one edge between two nodes of the graph. Also, there are no self loops are present in the graph. Now, you are allowed to do these two operations:

1 Remove an edge which is already present in the graph.

2 Add an edge between any two vertices of the graph.

The cost of removing or adding an edge is \(|node_1 - node_2|\) where \(node_1\) and \(node_2\) are the vertex numbers of \(node_1\) and \(node_2\) respectively and the edge being added or removed has \(node_1\) and \(node_2\) as its endpoints.

By performing the above mentioned operations as many times as you want, you need to convert the given graph into a single tree by using minimum possible cost. In the output, print the minimum cost required to achieve the given task.

Note: A tree is a graph which is connected and has no cycles.

Input:

First line will contain T as the number of test cases.

For each of the test case, first line will contain two integers N and M where N denotes the number of nodes and M denotes the number of edges in the graph respectively.

The next M lines contains two integers \(u_{i}\) and \(v_{i}\) denoting there is an undirected edge between \(u_{i}\) and \(v_{i}\).

Output:

For each of the test cases, print the required minimum cost in a separate line.

Constraints:

  • \(1 \le T \le 5\)

  • \(1 \le N, M \le 2 * 10^5\)

  • \( u_i \ne v_i \)

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

In the given test case, we can remove the edge between 2 and 3 and make the graph as a single tree. Hence, answer will be \(3 - 2 = 1\).

Time Limit: 2,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: 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

HackerEarth

Challenge Name

CodeMonk (CheckPoint III)

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?