Problem Description

As spring warms up and everything awakens, with the pandemic gradually subsiding, Yazid takes his $n$ friends to visit T University campus. For convenience, we number them from $1$ to $n$.

The layout of T University campus can be abstracted as an undirected graph with $n$ vertices (vertex numbers ranging from $1$ to $n$). For any two different vertices, let their numbers be $i$ and $j$ ($i \neq j$), there is an undirected edge between them that takes $|i - j|$ units of time to traverse.

Lilacs are one of the flowers of T University. As lilacs are in full bloom, $m$ paths on campus are adorned with lilacs. Yazid's friends are very interested in lilacs, so they all hope to traverse all $m$ paths that have lilacs.

Yazid's friends start from vertex $s$. Among them, the $i$-th friend hopes to end his visit at vertex $i$. At the same time, as mentioned above, each friend must pass through each of the $m$ lilac-adorned paths at least once.

Yazid's friends do not want to be too tired, so they hope to achieve their goal in the shortest possible time.

Please calculate how many units of time each of Yazid's friends needs to complete their goal.

Input Format

The first line contains three non-negative integers $n$, $m$, and $s$. It is guaranteed that $1 \le s \le n$; it is guaranteed that $m \le \frac{n(n-1)}{2}$.

From the second line to the $m+1$-th line, each line contains two integers $u$ and $v$, describing an undirected edge adorned with lilacs connecting vertices $u$ and $v$. It is guaranteed that $1 \le u, v \le n$ and $u \neq v$; it is guaranteed that each undirected edge is described at most once.

For all lines in the input, multiple integers within a line are separated by a single space.

Output Format

Output one line containing $n$ integers separated by a single space, where the $i$-th integer describes the minimum time required for Yazid's $i$-th friend to complete their goal.

Sample Input and Output

Input Sample #1

4 3 1
1 2
4 2
3 1

Output Sample #1

6 7 8 7

Input Sample #2

6 0 2

Output Sample #2

1 0 1 2 3 4

Input Sample #3

5 4 1
1 2
3 4
4 5
3 5

Output Sample #3

8 7 6 7 8

Notes

Sample Explanation 1

One optimal route for the $1$-st friend is to start from $1$, pass through $2, 4, 3$ in sequence, and finally return to $1$, consuming $|1-2|+|2-4|+|4-3|+|3-1| = 6$ units of time.

One optimal route for the $2$-nd friend is to start from $1$, pass through $2, 4, 3, 1$ in sequence, and finally arrive at $2$, consuming $7$ units of time.

One optimal route for the $3$-rd friend is to start from $1$, pass through $2, 4, 1$ in sequence, and finally arrive at $3$, consuming $8$ units of time.

One optimal route for the $4$-th friend is to start from $1$, pass through $3, 1, 2$ in sequence, and finally arrive at $4$, consuming $7$ units of time.

Sample Explanation 2

Since $m = 0$, there are no mandatory paths, so each friend can directly reach their destination via a single edge.

Data Range and Constraints

见题面 Input 部分

见题面 Output 部分