Shuffle

题意翻译

一个数列 $\{a_n\}$，开始只有 $a_x=1$，其余元素都等于 $0$。 你需要完成 $m$ 个操作，每个操作包含两个数 $l_i,r_i$。对于第 $i$ 个操作，你可以选择两个数 $c,d(l_i\le c,d\le r_i)$ ，并交换 $a_c,a_d$。 经过这些操作后，$a_k=1$。你的任务是计算满足条件的 $k$ 的个数。 Translated By [Sept](https://www.luogu.com.cn/user/224931)

题目描述

You are given an array consisting of $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ . Initially $ a_x = 1 $ , all other elements are equal to $ 0 $ . You have to perform $ m $ operations. During the $ i $ -th operation, you choose two indices $ c $ and $ d $ such that $ l_i \le c, d \le r_i $ , and swap $ a_c $ and $ a_d $ . Calculate the number of indices $ k $ such that it is possible to choose the operations so that $ a_k = 1 $ in the end.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then the description of $ t $ testcases follow. The first line of each test case contains three integers $ n $ , $ x $ and $ m $ ( $ 1 \le n \le 10^9 $ ; $ 1 \le m \le 100 $ ; $ 1 \le x \le n $ ). Each of next $ m $ lines contains the descriptions of the operations; the $ i $ -th line contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ).

输出格式

For each test case print one integer — the number of indices $ k $ such that it is possible to choose the operations so that $ a_k = 1 $ in the end.

输入输出样例

输入样例 #1

3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2

输出样例 #1

6
2
3

说明

In the first test case, it is possible to achieve $ a_k = 1 $ for every $ k $ . To do so, you may use the following operations: 1. swap $ a_k $ and $ a_4 $ ; 2. swap $ a_2 $ and $ a_2 $ ; 3. swap $ a_5 $ and $ a_5 $ . In the second test case, only $ k = 1 $ and $ k = 2 $ are possible answers. To achieve $ a_1 = 1 $ , you have to swap $ a_1 $ and $ a_1 $ during the second operation. To achieve $ a_2 = 1 $ , you have to swap $ a_1 $ and $ a_2 $ during the second operation.