P17771 开关灯 II

旅途中，小 D 住进了一间装有环形灯带的房间。睡觉前，他发现遥控器出了故障：每次操作都会同时切换连续的几盏灯。小 D 想用尽量少的操作把所有灯关掉。 灯带上共有 $n$ 盏灯，沿顺时针方向依次编号为 $0,1,\ldots,n-1$。其中，编号为 $n-1$ 的灯的下一盏是编号为 $0$ 的灯。 每次操作，小 D 可以任选一个编号 $p$，同时切换从 $p$ 开始、沿顺时针方向**连续的恰好 $k$ 盏灯**的状态，所选区间可以跨过圆环首尾。也就是说，编号为 $p,(p+1)\bmod n,\ldots,(p+k-1)\bmod n$ 的灯都会改变状态：亮灯变为灭灯，灭灯变为亮灯。不同操作可以选择相同的起点。 初始亮着的灯由 $m$ 个区间描述。第 $i$ 个区间为 $[l_i,r_i)$，表示编号满足 $l_i\le j

从标准输入读入数据。 第一行包含一个正整数 $T$，表示测试数据组数。 对于每组测试数据： - 第一行包含三个整数 $n,k,m$，分别表示灯的数量、每次操作切换的灯的数量，以及描述初始亮灯的区间数量。 - 接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示区间 $[l_i,r_i)$。

输出到标准输出。 对于每组测试数据，输出一行一个整数，表示最少操作次数；如果无解，输出 $-1$。

### 样例 1 解释 1. 第一组数据中，可以依次选择 $0,1,3$ 为起点进行操作，将所有灯关掉。最少需要 $3$ 次操作。 2. 第二组数据中，初始有 $3$ 盏亮灯。每次切换 $2$ 盏灯，亮灯数量的奇偶性不会改变，因此无法把所有灯关掉。 3. 第三组数据中，可以依次选择 $1,3$ 为起点进行操作。第二次操作会切换编号为 $3,0,1$ 的灯。 4. 第四组数据中，所有灯初始均为亮灯。分别以 $0,2,4$ 为起点操作即可。 5. 第五组数据中，两个给定区间首尾相接，初始亮灯的编号为 $1,2,3$。以 $1$ 为起点操作一次即可。 该样例同时保存在题目附件中的 `lights/lights1.in` 与 `lights/lights1.ans` 中。 ### 样例 2 见题目附件中的 `lights/lights2.in` 与 `lights/lights2.ans`。该样例满足特殊性质 B。 ### 样例 3 见题目附件中的 `lights/lights3.in` 与 `lights/lights3.ans`。该样例满足特殊性质 C。 ### 样例 4 见题目附件中的 `lights/lights4.in` 与 `lights/lights4.ans`。该样例满足全部数据的约束条件，不保证满足任何特殊性质。 ### 数据范围与测试点 对于全部数据，保证： - $1\le T\le 10^5$； - $2\le n\le 10^9$，$1\le k