解题思路

先把题意转化一下。

你需要选一个整数位置 $x$，要求它不能落在任何一个人的禁区 $[l_i, r_i]$ 中，也就是 $x$ 不能被这些区间的并集覆盖。同时要让你走的距离 $|x-p|$ 最小。

所以问题本质上就是：

给定若干个区间，求离 $p$ 最近的、不在这些区间并集内 的整数点。

题目内容

在一条无限长的美食街上，每个整数坐标处都有一家餐厅。你当前位于位置 $p$。

现在共有$n$个人（包括你自己），第$i$ 个人不愿意去区间$[l_i,r_i]$内的任何餐厅。你需要选择一个餐厅位置$x∈Z$，使得对所有人都 “可接受”（即$x\notin [l_i,r_i]$对所有 $i$成立），并且使你走的距离$∣x−p∣$ 最小。请输出这个最小距离。

输入描述

每个测试文件均包含多组测试数据：第一行输入一个整数$T(1≤T≤2×10^5)$，代表数据组数。每组测试数据描述如下：

• 每组数据第一行输入两个整数 $n,p(1≤n≤2×10^5，−10^6≤p≤10^6)$；
• 接下来 $n$ 行，每行输入两个整数 $l_i,r_i(−10^6≤l_i≤r_i≤10^6)$。

保证所有测试中 $n$的总和不超过 $5×10^5$。

输出描述

输出$T$行，每行输出一个整数，为最小距离。

样例1

输入

3
2 5
1 3
7 8
1 10
10 20
3 0
-2 1
2 4
6 9

输出

0
1
3

说明

• 样例$1$：禁用区间为$[1,3]∪[7,8]$，位置$p=5$可直接就餐，距离为$0$。
• 样例 $2$：最近不在禁区内的餐厅位置是$9$，距离为$∣9−10∣=1$。