 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Third qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  5 seconds 

Memory limit  256 megabytes 
Andrew is analyzing subscription graph in one social network. This graph is directed: if the user a is subscribed to the user b, it is not always the case that the user b is in turn subscribed to the user a.
Andrew's boss has asked him to find for each user x the number of users y such that it is possible to reach user y from user x in the subscription graph.
There is no reason to find the exact values, they look ugly and are nonrelevant almost immediately, so Andrew wants to find approximate values. Find values that differ from the correct ones at most by a factor of two.
Input format 
The first line of input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of users of the social network and the number of direct subscriptions. The following m lines describe subscription graph, the ith of these lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}), it means that the user a_{i} is subscribed to the user b_{i}. Each ordered pair (a_{i}, b_{i}) occurs at most once in the input data. 

Output format 
Output n integers q_{i} — for each user print approximate number of users y such that it is possible to reach user y from user i in the subscription graph. If the correct number of such users is z_{i}, the following inequalities must be satisfied to have the answer accepted: q_{i} ≤ 2z_{i} and z_{i} ≤ 2q_{i}. Moreover, you are allowed to bypass this restriction and output any q_{i} for no more than 10 users. Note: judges use exact values to check your answers. However, judges don't promise that it is possible to find exact values in each test case given time and memory constraints of this problem. They recommend to try to find approximate value. In the given example it is possible to reach all five users from the user 1. But the given answer 7 is acceptable, it differs from 5 less than by a factor of two. Similarly, the answer 2 is acceptable for the user 4. 
Examples 
Input data
5 6 1 2 1 3 2 4 2 5 3 5 4 2
Output data
7 3 2 2 1 
