#2313. 「CSP-S 2022」数据传输 暂未评定

时间限制:1000 ms 内存限制:128 MiB 输入文件:transmit.in 输出文件:transmit.out
题目类型:传统 评测方式:文本比较
上传者: root

注意

本题采用文件输入输出。

输入文件为 transmit.in, 输出文件为transmit.out

题目描述

小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有 台主机,依次编号为 。这 台主机之间由 根网线连接,第 条网线连接个主机 。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率,主机 能够直接将信息传输给主机 当且仅当两个主机在可以通过不超过 根网线直接或者间接的相连。

在计算机网络中,数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 传输到主机 ),则其会选择出若干台用于传输的主机 ,并按照如下规则转发:对于所有的 ,主机 将信息直接发送给

每台主机处理信息都需要一定的时间,第 台主机处理信息需要 单位的时间。数据在网络中的传输非常迅速,因此传输的时间可以忽略不计。据此,上述传输过程花费的时间为

现在总共有 次数据发送请求,第 次请求会从主机 发送数据到主机 。小 C 想要知道,对于每一次请求至少需要花费多少单位时间才能完成传输。

输入格式

从文件 transmit.in 中读入数据。

输入的第一行包含三个正整数 ,分别表示网络主机个数,请求个数,传输参数。数据保证

输入的第二行包含 个正整数,第 个正整数表示 ,保证

接下来 行,第 行包含两个正整数 ,表示一条连接主机 的网线。保证

接下来 行,第 行包含两个正整数 ,表示一次从主机 发送数据到主机 的请求。保证

输出格式

输出到文件 transmit.out 中。

行,每行一个正整数,表示第 次请求在传输的时候至少需要花费多少单位的时间。

样例

样例输入 1

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

样例输出 1

12
12
3

样例解释 1

对于第一组请求,由于主机 之间需要至少 根网线才能连接,因此数据无法在两台主机之间直接传输,其至少需要一次转发;我们让其在主机 进行一次转发,不难发现主机 和主机 之间都只需要两根网线即可连接,且主机 的数据处理时间仅为 ,为所有主机中最小,因此最少传输的时间为

对于第三组请求,由于主机 之间只需要 根网线就能连接,因此数据直接传输就是最优解,最少传输的时间为

样例2

见附件中的 transmit2.intransmit2.ans

该样例满足测试点 的限制。

样例3

见附件中的 transmit3.intransmit3.ans

该样例满足测试点 的限制。

样例4

见附件中的 transmit4.intransmit4.ans

该样例满足测试点 的限制。

数据范围与提示

对于所有的测试数据,满足

测试点 特殊性质

特殊性质:保证 ,而 则从 中等概率选取。