P17649 [IO 2025 #1] 骷髅、骨头、墓地、头骨

法鲁姆（Farloom）是一个遍布丝线小径的王国。每条小径都是连接两个村庄的一根绷紧的直丝线。狡猾的反派“头骨暴君”打算沿竖直方向挥击这张由小径组成的网。 把王国看成一张图：顶点是村庄，第 $i$ 个村庄在平面上的坐标为 $(x_i,y_i)$；边是连接村庄的丝线小径。表示道路的线段可以在村庄之外相交，但不能在这些交点处从一条道路转到另一条道路。 王国居民猜测了 $q$ 个暴君可能攻击的位置。如果暴君沿横坐标为 $X$ 的竖直直线攻击，将删除： - 所有满足 $x_i=X$ 的村庄； - 所有连接村庄 $i,j$ 且满足 $\min(x_i,x_j)\le X\le\max(x_i,x_j)$ 的道路。 请帮助居民，对每个可能的攻击位置，求攻击后王国中剩余的连通分量数。所有询问相互独立：回答当前询问时，不需要考虑之前的攻击。 图的连通分量是一个顶点集合，集合中的任意顶点都可以沿边到达集合内的其他任意顶点，但不能沿边到达集合之外的顶点。

每个测试包含多组数据。第一行包含整数 $t$，表示数据组数，满足 $1\le t\le5000$。接下来依次描述每组数据。 每组数据的第一行包含三个整数 $n,m,q$，分别表示村庄数、道路数和可能的攻击位置数，满足 $1\le n\le10^5$，$0\le m\le\min(10^5,\frac{n(n-1)}2)$，$1\le q\le10^5$。 第二行包含 $n$ 个整数 $x_i$，表示各村庄的横坐标。第三行包含 $n$ 个整数 $y_i$，表示各村庄的纵坐标。坐标范围为 $-10^9\le x_i,y_i\le10^9$。 接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示道路连接的两个村庄编号，满足 $1\le u_i,v_i\le n$，且 $u_i\ne v_i$。 最后一行包含 $q$ 个整数，表示各个可能攻击位置的横坐标，每个数的绝对值都不超过 $10^9$。 保证同一组数据中，没有两个村庄的坐标相同。保证所有数据组的 $n$ 之和、$m$ 之和、$q$ 之和分别都不超过 $10^5$。

对每组数据，输出一行 $q$ 个整数，分别表示各询问的答案。 注意，各询问相互独立。

样例中的图如下所示： :::align{center}  :::