P4155 [SCOI2015] National Flag Plan

Country A is carrying out a great plan — the National Flag Plan. In this plan, border guards will run a full loop along the border line in relay while holding the national flag. This requires multiple border guards working together in relay. The National Security Agency has selected $N$ outstanding border guards as candidates. Country A is vast, and there are $M$ border posts on the border line, numbered $1$ to $M$ clockwise. Each border guard is based at two border posts and is skilled at long-distance running between these two posts. We call the path between these two posts the guard’s running interval. The $N$ guards are carefully selected and in excellent physical condition, so no guard’s running interval is contained within another guard’s running interval. The director of the National Security Agency wants to know the minimum number of border guards whose running intervals can cover the entire border line to successfully complete the National Flag Plan. Moreover, for each border guard, under the condition that he must participate, the director also wants to know the minimum number of border guards required to cover the entire border line.

The first line contains two positive integers $N, M$, the number of border guards and the number of border posts. Then follow $N$ lines, each containing two positive integers. On the $i$-th line, the two integers $C_i, D_i$ denote the indices of the two border posts where guard $i$ is based. The running interval of guard $i$ is from post $C_i$ to post $D_i$ in the clockwise direction. It is guaranteed that the entire border line can be covered.

Output a single line containing $N$ positive integers. The $j$-th integer denotes, under the condition that guard $j$ must participate, the minimum number of border guards required to successfully complete the National Flag Plan.

Constraints: $N \leq 2 \times 10^5, M < 10^9, 1 \leq C_i, D_i \leq M$. Translated by ChatGPT 5