Problem Description

As spring arrives and everything comes back to life, with the pandemic gradually ending, Yazid takes his $n$ good friends to visit the campus of University T. For convenience, we number them from $1$ to $n$.

The map of University T’s campus can be abstracted as an undirected graph with $n$ vertices (numbered from $1$ to $n$). For any two different vertices with indices $i, j$ $(i \neq j)$, there is an undirected edge between them, and it takes $|i - j|$ units of time to traverse.

Lilac is one of the symbolic flowers of University T. At present, lilacs are in bloom, and among the $m$ roads on campus, lilacs bloom on all of them. Yazid’s friends are very interested in lilacs, so they all want to traverse all of the $m$ roads where lilacs bloom.

Yazid’s friends start from vertex $s$. The $i$-th friend wants to end the visit at vertex $i$. Meanwhile, as described above, each friend must traverse each of the $m$ roads with lilacs at least once.

Yazid’s friends do not want to get too tired, so they hope to spend as little time as possible to achieve their goals.

Please compute how many units of time each of Yazid’s friends needs to spend to complete their goal.

Input Format

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

Lines $2$ to $m+1$ each contain $2$ integers $u, v$, describing an undirected edge with lilacs that connects vertices $u, v$. It is guaranteed that $1 \le u, v \le n$ and $u \neq v$; and each undirected edge is described at most once.

In every input line, multiple integers are separated by a single space.

Output Format

Output one line containing $n$ integers separated by a single space. The $i$-th integer indicates the minimum time Yazid’s $i$-th friend needs to complete the goal.

4 3 1
1 2
4 2
3 1

6 7 8 7

6 0 2

1 0 1 2 3 4

5 4 1
1 2
3 4
4 5
3 5

8 7 6 7 8

Hint

Sample Explanation 1

One optimal route for the $1$-st friend is to start from $1$, then go through $2, 4, 3$ in order, and finally return to $1$, costing $|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$, then go through $2, 4, 3, 1$ in order, and finally arrive at $2$, costing $7$ units of time.

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

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

Sample Explanation 2

Since $m = 0$, there are no mandatory roads, so each friend can go directly to the destination via a single edge.

Constraints and Notes

Translated by ChatGPT 5