#5kfew1. 丁香之路

时间限制：2 s       空间限制：512 MiB       标签： 图论 欧拉路 省选 2020 

算法难度等级：6       思维难度等级：5       实现难度等级：5

题目大意

给定一个有 $n$ 个点，$m$ 条边的无向图以及一个起点 $s$。

对于任意一个点，找出最短的一条从 $s$ 到这个点的路径经过这 $m$ 条边，路径中可以从任意一个点 $i$ 走到另一个点 $j$，无论是否在给定的 $m$ 条边中，边权均为 $|i-j|$。

$50\leq n\leq 2500$，$0\leq m\leq\dbinom n2$

题目描述

春暖花开，万物复苏，随着疫情的逐渐过去，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$ 个朋友完成目标所需花费的最少时间。

样例输入输出

4 3 1
1 2
4 2
3 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$ 单位时间。

6 0 2

1 0 1 2 3 4

样例解释 2

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

5 4 1
1 2
3 4
4 5
3 5

8 7 6 7 8

数据范围