P1137 Travel Plan

Xiao Ming is going to travel to a country. This country has $N$ cities, numbered $1$ to $N$, and there are $M$ roads connecting them. Xiao Ming plans to start from some city and only move east until he stops at city $i$. Therefore, for each city $i$, he needs to choose a starting city and plan a route ending at city $i$, such that along the route, except for the first city, every city lies to the east of the previous city. Under this condition, he also wants to visit as many cities as possible. You only know the relative east–west positions of the two cities connected by each road, but you do not know the exact positions of all cities. Now, for every $i$, you need to plan a route for Xiao Ming and compute the maximum number of cities that can be visited on a route ending at city $i$.

The first line contains two positive integers $N, M$. The next $M$ lines each contain two positive integers $x, y$, indicating there is a road connecting city $x$ and city $y$, and it is guaranteed that city $x$ is to the west of city $y$.

Output $N$ lines. The $i$-th line contains a positive integer, the maximum number of cities that can be visited on a route ending at city $i$.

Choosing to always start from city $1$ yields the answers. Constraints: - For $20\%$ of the testdata, $1 \le N \le 100$. - For $60\%$ of the testdata, $1 \le N \le 1000$. - For $100\%$ of the testdata, $1 \le N \le 100000$, $1 \le M \le 200000$. Translated by ChatGPT 5