Maximum City Visits on an Eastern Route

Little Ming plans to travel in a country that consists of \(N\) cities, numbered from 1 to \(N\), and there are \(M\) directed roads connecting these cities. Each road connects two cities and indicates that one city is to the west of the other. In other words, if a road is given as \(u\) to \(v\), then city \(u\) is to the west of city \(v\). Little Ming starts his tour at any city and moves strictly eastward. That is, except for the first city he visits, every subsequent city must be strictly east of the previous one, and there must be a road from the previous city to the next city in his route.

For each city \(i\) (where \(1 \le i \le N\)), your task is to determine the maximum number of cities that can be visited in a valid route that ends at city \(i\). Note that if a city has no incoming road on a valid route, it can serve as the starting point and the route will count only that city.

Hint: You may represent the road network as a directed acyclic graph (DAG) and use dynamic programming or topological sorting to compute the longest path ending at each city. The length of a path is defined as the number of cities visited.

The relation can be expressed using the following recurrence formula: \[ dp[i] = \max(1,\;\max_{j \rightarrow i} (dp[j] + 1)) \] where \(j \rightarrow i\) indicates there is a road from city \(j\) to city \(i\).

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of cities and roads respectively. The following \(M\) lines each contain two integers \(u\) and \(v\) indicating there is a road from city \(u\) (west) to city \(v\) (east).

outputFormat

Output a single line containing \(N\) integers. The \(i\)-th integer represents the maximum number of cities that can be visited in a valid route ending at city \(i\).

sample

4 4
1 2
1 3
2 4
3 4

1 2 2 3