← 返回题目列表

Codeforces · 1843/E

E. 跟踪段

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 零组成的数组 $$$a$$$。您还会获得一组 $$$m$$$ 不一定是不同的段。每个段由两个数字 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) 定义,表示数组 $$$a$$$ 的子数组 $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$。

如果 $$$l_i, r_i$$$ 段上 1 的数量严格大于 0 的数量,那么我们称该段为“漂亮”。例如,如果 $$$a = [1, 0, 1, 0, 1]$$$,则段 $$$[1, 5]$$$ 很漂亮(1 的数量为 $$$3$$$,零的数量为 $$$2$$$),但段 $$$[3, 4]$$$ 则不漂亮(1 的数量为 $$$1$$$,零的数量为 $$$1$$$ $$$1$$$)。

您还有 $$$q$$$ 更改。对于每个更改,您都会获得数字 $$$1 \le x \le n$$$,这意味着您必须为元素 $$$a_x$$$ 分配值 $$$1$$$。

您必须找到第一个更改,之后至少有一个给定的 $$$m$$$ 段变得漂亮,或者报告在处理所有 $$$q$$$ 更改后没有一个是漂亮的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 10^5$$$) - 分别是数组 $$$a$$$ 的大小和段数。

然后有 $$$m$$$ 行,由两个数字 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) 组成 - 线段的边界。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le n$$$) — 更改数量。

以下 $$$q$$$ 行每行包含一个整数 $$$x$$$ ($$$1 \le x \le n$$$) — 需要设置为 $$$1$$$ 的数组元素的索引。保证查询中的索引是不同的。

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

输出

对于每个测试用例,输出一个整数 - 最小变化数,在此之后至少有一个片段将变得漂亮,或者如果没有一个片段将变得漂亮,则输出 $$$-1$$$。

示例

输入 #1

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

输出 #1

3
-1
3
3
3
1

注意

在第一种情况下,在前 2 个更改之后,我们不会有任何漂亮的片段,但是在片段 $$$[1; 上的第三个更改之后5]$$$ 将有 3 个 1,只有 2 个 0,所以答案是 3。

第二种情况,不会有任何漂亮的片段。