Another Contest 7 Problem 3 - Network Connections

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.75s
Memory limit: 256M

Problem type

Ren has recently created a website, Ternary Search, which he intends on turning into the premier platform for competitive programmers to talk about anything.

Ren's website has slowly become more and more popular - it currently has N users, user i having a unique friendliness value f_i that is a positive integer no larger than one billion.

Ren wants to make sure that any user is able to communicate with any other user on the platform. Two users can directly communicate with each other if and only if they are friends, so two users a and b can communicate if they are friends with each other, or if there is some sequence of users a, u_1, \dots, u_k, b such that adjacent users in the sequence are friends.

Ren knows which users are friends with each other, and can force users i and j to be friends with cost |f_i - f_j|. Compute the minimum cost Ren needs to incur such that any two users on the platform can communicate with each other.


1 \le N \le 10^5

0 \le M \le 10^5

1 \le f_i \le 10^9

f_i < f_j \Leftrightarrow i < j

1 \le x < y \le N

Input Specification

The first line contains two space-separated positive integers N and M.

The next line contains N space-separated integers, the f_i values for the N users in order.

The next M lines each contain two space-separated integers x and y, indicating that users x and user y are already friends. It is guaranteed that every friendship already present is expressed exactly once.

Output Specification

Output the minimum cost needed to make sure any two users can communicate.

Sample Input

4 2
1 2 3 4
1 2
3 4

Sample Output



There are no comments at the moment.