#3310. 「联合省选 2020 B」丁香之路

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

春暖花开,万物复苏,随着疫情的逐渐过去,Yazid 带着他的 n 个好朋友来到 T 大校园参观游览。方便起见,我们将他们从 1 n 编号。

T 大校园的版图可以抽象成一张 n 个顶点的无向图(顶点编号从 1 n )。且对于任意两个不同顶点,设它们的编号分别为 i, j i \neq j ),则它们之间有一条需要花费 |i - j| 单位时间通过的无向边。

丁香花是 T 大的校花之一。时下正值丁香花盛开之际,校园内的 m 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣,因此他们都希望遍历所有开有丁香花的 m 条道路。

Yazid 的朋友们从顶点 s 出发。其中,第 i 个朋友希望以顶点 i 为终点终止他的参观。与此同时,如上面所述,每个朋友都必须经过开着丁香花的 m 条道路各至少一次。

Yazid 的朋友不想太过疲累,因此他们希望花尽可能少的时间来完成他们的目标。 请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。

输入格式

第一行 3 个非负整数 n, m, s 。保证 1\le s\le n ;保证 m\le \frac {n(n-1)}2

2 行至第 m+1 行,每行 2 个整数 u, v ,描述一条开有丁香花的,连接顶点 u, v 的无向边。保证 1\le u, v\le n u\neq v ;保证每条无向边至多被描述一次。

对于输入的所有行,用单个空格将行内的多个整数隔开。

输出格式

输出一行 n 个用单个空格隔开的整数,其中第 i 个整数描述 Yazid 的第 i 个朋友完成目标所需花费的最少时间。

样例

样例输入 1

4 3 1
1 2
4 2
3 1

样例输出 1

6 7 8 7

样例解释 1

1 个朋友的一种最优路线是从 1 出发依次途径 2, 4, 3 ,最终回到 1 ,消耗 |1-2|+|2-4|+|4-3|+|3-1| = 6 单位时间。

2 个朋友的一种最优路线是从 1 出发依次途径 2, 4, 3, 1 ,最终来到 2 ,消耗 7 单位时间。

3 个朋友的一种最优路线是从 1 出发依次途径 2, 4, 1 ,最终来到 3 ,消耗 8 单位时间。

4 个朋友的一种最优路线是从 1 出发依次途径 3, 1, 2 ,最终来到 4 ,消耗 7 单位时间。

样例输入 2

6 0 2

样例输出 2

1 0 1 2 3 4

样例解释 2

由于 m = 0 ,没有必经之路,因此每个朋友直接通过一条边直达目的地即可。

样例输入 3

5 4 1
1 2
3 4
4 5
3 5

样例输出 3

8 7 6 7 8

数据范围与提示

测试点编号 n= 其他特殊限制
1\sim 3 50 m=9
4\sim 6 m=15
7\sim 8
9\sim 10 300
11 1600 m=0
12\sim 14 m=1
15\sim 17
18\sim 20 2500