#P18917. [2026多校联测]清仓甩卖
[2026多校联测]清仓甩卖
清仓甩卖
题目描述
商场共有 个摊位,编号为 ,由 条双向通道连接。保证商场连通,允许重边和自环。
对于一条行走路线,记录依次经过的摊位编号 。若 比之前经过的所有编号都大,即不存在 使 ,则称它为一个“价格新高”摊位。
路线的“刺激程度”是其中“价格新高”摊位的个数。有 位顾客,每人从 出发到达 ,可以重复经过通道或摊位。请分别求出最小的刺激程度。
输入格式
第一行四个正整数 ,其中 为子任务编号。
接下来 行,每行两个正整数 ,表示一条双向通道。
接下来 行,每行两个正整数 ,表示一位顾客的起点和终点。
输出格式
输出 行,每行一个正整数,表示对应顾客的最小刺激程度。
样例 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
样例解释

- 询问 :可走 ,价格新高为 ,答案为 。
- 询问 :可走 ,只有 是价格新高,答案为 。
- 询问 :可走 ,价格新高为 ,答案为 。
- 询问 :可走 ,价格新高为 ,答案为 。
数据范围
对于所有数据,,所有点编号属于 ,图连通。
| 子任务 | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 1 | 无 | 10 | ||
| 2 | 20 | |||
| 3 | ||||
| 4 | A | 5 | ||
| 5 | B | 15 | ||
| 6 | C | 10 | ||
| 7 | 无 | 20 | ||
- A:只有 号点的度数可以大于 。
- B:所有询问的起点 相同。
- C:对于任意 ,点集 的导出子图连通。
更多样例见附加文件 samples.zip。