Bear and Almost Row

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Bearland has N cities, numbered 1 through N. For every i between 1 and N1 inclusive, there is a road between cities i and i+1. There K extra roads: the ith of them connects two different cities a_{i} and b_{i}. So, there are N1+K roads in total. All roads are bidirectional.
You can assume that every two cities are connected by at most one road.
Let f(s, t) denote the distance between cities s and t, i.e. the minimum possible number of roads needed to get from one city to the other.
Your task is to find the sum of f(s, t) over all pairs of cities (s, t) such that s < t.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the number of cities.
The second line contains an integer K denoting the number of extra roads. Note the unusual constraint for K (in the constraints section below).
The ith of the following K lines contains two different integers a_{i} and b_{i}, denoting cities connected by the ith road. All N1+K roads will be distinct.
Output
For each test case, output a single line containing one integer — the sum of f(s, t) over all pairs (s, t) such that s < t. For the given constraints, it can be proved that the answer fits in the 64bit signed type.
Constraints
 1 ≤ T ≤ 1000
 2 ≤ N ≤ 10^{6}
 0 ≤ K ≤ 10
 1 ≤ a_{i}, b_{i} ≤ N
 a_{i} ≠b_{i}
 All N1+K roads will be distinct.
Subtasks
 Subtask #1 (15 points): 2 ≤ N ≤ 40
 Subtask #2 (35 points): The sum of N in all test cases won't exceed 200,000.
 Subtask #3 (15 points): 0 ≤ K ≤ 1
 Subtask #4 (35 points): Original constraints.
Example
Input: 4 4 2 1 3 4 1 5 1 2 5 20 3 1 7 3 12 17 19 1000000 0 Output: 7 16 891 166666666666500000
Explanation
The provided example test contains T = 4 test cases. The following drawings show the situation for the first two test cases (extra roads are red):
In the first test case, there are 4 cities and 2 extra roads 13 and 41. So we have 5 roads in total: 12, 13, 14, 23, 34 (see the left drawing). The sought values are:
 f(1, 2) = f(1, 3) = f(1, 4) = f(2, 3) = f(3, 4) = 1
 f(2, 4) = 2
The answer is 1 + 1 + 1 + 1 + 1 + 2 = 7.
Author:  errichto 
Tester:  kingofnumbers 
Tags  errichto, floydwarshall, hard, ltime46, shortestpath 
Date Added:  24032017 
Time Limit:  2.5  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions