Lilac Tour on the Campus

T university has a campus that can be represented as a complete undirected graph with n vertices numbered from 1 to n. For any two distinct vertices i and j, there is an edge connecting them with a travel time of \(|i-j|\) (in units of time).

Among these roads, m of them are special – they have blooming lilacs. Yazid brought his n friends (numbered 1 through n) to tour the campus. All of his friends start their tour from vertex s. Furthermore, the i-th friend intends to finish his tour at vertex i, and each friend must traverse every one of the m lilac roads (i.e. the corresponding special edges) at least once.

The task is to help each friend minimize the total travel time needed to achieve his goal.

Note: The graph is complete and the cost between any two vertices i and j is \(|i-j|\). When m = 0 (i.e. there are no lilac roads), a friend’s route is simply a direct travel from the starting point to his designated endpoint.

Hint: If there is at least one special road then for each road connecting vertices \(u\) and \(v\) we can define an interval \([\min(u,v),\max(u,v)]\). Let \(L\) be the minimum over all these and \(R\) be the maximum. It can be shown that the minimum travel time for a friend to cover the interval \([L,R]\) (thereby covering every special edge) while starting from \(s\) and finishing at vertex \(t\) is:

[ \text{Cost} = (R - L) + \min\bigl(|s - L| + |t - R|,;|s - R| + |t - L|\bigr). ]

When m = 0, the answer is simply \(|s-t|\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(s\) \( (1 \leq s \leq n)\), representing the number of vertices, the number of special roads (lilac roads), and the starting vertex respectively.

Then, there are \(m\) lines, each containing two integers \(u\) and \(v\) (\(1 \le u,v \le n\), \(u \neq v\)) indicating that there is a special road between vertices \(u\) and \(v\).

If \(m = 0\), no additional lines are present.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain one integer representing the minimum travel time required for the \(i\)-th friend to complete his tour (starting from \(s\) and finishing at vertex \(i\)) while ensuring that every special road is traversed at least once.

sample

5 2 3
1 2
4 5

6
7
8
7
6