codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]