1771B.md (1978B)
1 Source: https://codeforces.com/problemset/problem/1771/B 2 3 B. Hossam and Friends 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hossam makes a big party, and he will invite his friends to the party. 22 23 He has $n$ friends numbered from $1$ to $n$. They will be arranged in a queue as follows: $1, 2, 3, \ldots, n$. 24 25 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. 26 27 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. 28 29 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. 30 31 Input 32 33 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. 34 35 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. 36 37 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. 38 39 Note that pairs can be repeated. 40 41 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$. 42 43 Output 44 45 For each test case print an integer — the number of good subsegments. 46 47 Example 48 49 Input 50 51 ``` 52 2 53 54 3 2 55 56 1 3 57 58 2 3 59 60 4 2 61 62 1 2 63 64 2 3 65 ``` 66 67 Output 68 69 ``` 70 4 71 5 72 ``` 73 74 Note 75 76 In the first example, the answer is $4$. 77 78 The good subsegments are: 79 80 [1] 81 82 [2] 83 84 [3] 85 86 [1, 2] 87 88 In the second example, the answer is $5$. 89 90 The good subsegments are: 91 92 [1] 93 94 [2] 95 96 [3] 97 98 [4] 99 100 [3, 4]