Codeforces Round 837 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

constructive algorithms

dp

two pointers

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Hossam and Friends

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHossam makes a big party, and he will invite his friends to the party.

He has $$$n$$$ friends numbered from $$$1$$$ to $$$n$$$. They will be arranged in a queue as follows: $$$1, 2, 3, \ldots, n$$$.

Hossam has a list of $$$m$$$ pairs of his friends that don't know each other. Any pair not present in this list are friends.

A subsegment of the queue starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is $$$[a, a + 1, a + 2, \ldots, b]$$$. A subsegment of the queue is called good when all pairs of that segment are friends.

Hossam wants to know how many pairs $$$(a, b)$$$ there are ($$$1 \le a \le b \le n$$$), such that the subsegment starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is good.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$), the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) representing the number of friends and the number of pairs, respectively.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$) representing a pair of Hossam's friends that don't know each other.

Note that pairs can be repeated.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case print an integer — the number of good subsegments.

Example

Input

23 21 32 34 21 22 3

Output

4 5

Note

In the first example, the answer is $$$4$$$.

The good subsegments are:

[1]

[2]

[3]

[1, 2]

In the second example, the answer is $$$5$$$.

The good subsegments are:

[1]

[2]

[3]

[4]

[3, 4]

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 11:59:17 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|