Counting Inversions After Swaps

In this problem, you are given a sequence of abilities over n days. Initially, on day i the ability is S_i = i (i.e., the ability on day 1 is 1, on day 2 is 2, and so on). However, a mischievous twist occurs when a time-machine is used to swap the abilities of two days.

You are given q operations. Each operation specifies two days x and y where the ability values are swapped, i.e.:

$S_x \leftrightarrow S_y$

After performing all q swaps, your task is to compute the number of inversion pairs in the final sequence. An inversion pair is defined as a pair of days (x, y) with x < y and S_x > S_y.

Input Format (detailed below): The first line contains two integers n and q. Then q lines follow, each containing two integers x and y (1-based indices) indicating a swap between day x and day y.

Output Format: Output a single integer representing the number of inversion pairs in the final ability sequence.

Recall the inversion definition in formal mathematical notation: Find the number of pairs \((x, y)\) such that $$1 \le x S_y.$$

Note: You must compute the answer in under 1 second.

inputFormat

The first line of the input contains two integers n and q separated by a space, where n is the number of days and q is the number of swap operations. Each of the next q lines contains two integers x and y (1-based indexing) indicating that the ability values on day x and day y are swapped.

outputFormat

Output a single integer — the number of inversion pairs in the final sequence after all swap operations have been performed.

sample

3 1
1 3

3