P6348 [PA 2011] Journeys

On a planet, there are $n$ countries and many bidirectional roads. The countries are numbered from $1$ to $n$. However, there are too many roads to describe in the usual way. So we describe the roads as follows: $(a,b),(c,d)$ means that for any two countries $x,y$, if $a \le x \le b$ and $c \le y \le d$, then there is a road between $x$ and $y$. The capital is located in country $P$. You want to know the minimum number of roads that must be taken to travel from country $P$ to any country. It is guaranteed that country $P$ can reach every country.

The first line contains three integers $n,m,P$. Then follow $m$ lines, each containing four integers $a,b,c,d$.

Output $n$ lines. The $i$-th line should contain the minimum number of roads that must be taken to travel from country $P$ to country $i$.

For all testdata, it is guaranteed that $1 \le n \le 5 \times 10^5$, $1 \le m \le 10^5$, $1 \le a \le b \le n$, $1 \le c \le d \le n$. Translated by ChatGPT 5