#P18917. [2026多校联测]清仓甩卖

[2026多校联测]清仓甩卖

清仓甩卖

题目描述

商场共有 nn 个摊位,编号为 1∼n1\sim n,由 mm 条双向通道连接。保证商场连通,允许重边和自环。

对于一条行走路线,记录依次经过的摊位编号 p1,p2,…,pkp_1,p_2,\ldots,p_k。若 pip_i 比之前经过的所有编号都大,即不存在 1≤j<i1\le j<i 使 pj≥pip_j\ge p_i,则称它为一个“价格新高”摊位。

路线的“刺激程度”是其中“价格新高”摊位的个数。有 qq 位顾客,每人从 ss 出发到达 tt,可以重复经过通道或摊位。请分别求出最小的刺激程度。

输入格式

第一行四个正整数 id,n,m,qid,n,m,q,其中 idid 为子任务编号。

接下来 mm 行,每行两个正整数 u,vu,v,表示一条双向通道。

接下来 qq 行,每行两个正整数 s,ts,t,表示一位顾客的起点和终点。

输出格式

输出 qq 行,每行一个正整数,表示对应顾客的最小刺激程度。

样例 1

输入

2 8 10 4
1 8
2 5
3 6
2 6
3 8
1 6
2 1
4 8
3 4
6 7
2 3
4 3
5 4
3 8

输出

2
1
2
2

样例解释

商场地图

  • 询问 (2,3)(2,3):可走 (2,6,3)(2,6,3),价格新高为 2,62,6,答案为 22。
  • 询问 (4,3)(4,3):可走 (4,3)(4,3),只有 44 是价格新高,答案为 11。
  • 询问 (5,4)(5,4):可走 (5,2,6,3,4)(5,2,6,3,4),价格新高为 5,65,6,答案为 22。
  • 询问 (3,8)(3,8):可走 (3,8)(3,8),价格新高为 3,83,8,答案为 22。

数据范围

对于所有数据,1≤n,m,q≤5×1051\le n,m,q\le5\times10^5,所有点编号属于 [1,n][1,n],图连通。

子任务 n,m≤n,m\le q≤q\le 特殊性质 分值
1 55 无 10
2 100100 20
3 30003000
4 5×1055\times10^5 A 5
5 B 15
6 C 10
7 无 20
  • A:只有 11 号点的度数可以大于 11。
  • B:所有询问的起点 ss 相同。
  • C:对于任意 1≤i≤n1\le i\le n,点集 {1,2,…,i}\{1,2,\ldots,i\} 的导出子图连通。

更多样例见附加文件 samples.zip。