×

计蒜客

  1. 题库
  2. Light bulbs
  3. 问答
  • 20.09%
  • 8192K

There are $N$ light bulbs indexed from $0$ to $N-1$. Initially, all of them are off.

A FLIP operation switches the state of a contiguous subset of bulbs. $FLIP(L, R)$ means to flip all bulbs $x$ such that $L \leq x \leq R$. So for example, $FLIP(3, 5)$ means to flip bulbs $3$ , $4$ and $5$, and $FLIP(5, 5)$ means to flip bulb $5$.

Given the value of $N$ and a sequence of $M$ flips, count the number of light bulbs that will be on at the end state.

InputFile

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers $N$ and $M$, the number of light bulbs and the number of operations, respectively. Then, there are $M$ more lines, the $i$-th of which contains the two integers $L_i$ and $R_i$, indicating that the $i$-th operation would like to flip all the bulbs from $L_i$ to $R_i$ , inclusive.

$1 \leq T \leq 1000$

$1 \leq N \leq 10^6$

$1 \leq M \leq 1000$

$0 \leq L_i \leq R_i \leq N-1$

OutputFile

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the number of light bulbs that will be on at the end state, as described above.

样例输入

2
10 2
2 6
4 8
6 3
1 1
2 3
3 4

样例输出

Case #1: 4
Case #2: 3

想挑战这道题吗

  • main.c