Prerequisite Courses

Minwook entered the computer science department of Z University this year, and he wants to take every major course the department offers before he graduates. Some courses have prerequisites: he can take such a course only after he has completed all of its prerequisites. Minwook refuses to give up on engineering accreditation, so he must respect every prerequisite. He wants to know when he can take each major course while respecting them. To keep the calculation simple he settled on these rules.

1. There is no limit on how many courses he takes in one semester.
2. Every course is offered every semester.

Write a program that computes, for every course, the smallest number of semesters needed to complete it.

The first line contains the number of courses $N$ ($1 \le N \le 1000$) and the number of prerequisite conditions $M$ ($0 \le M \le 500\,000$).

Each of the next $M$ lines contains one condition as two integers $A$ $B$, meaning that course $A$ is a prerequisite of course $B$. The input contains only conditions with $A < B$ ($1 \le A < B \le N$). The same condition may appear more than once.

Print, for courses $1$ through $N$ in order, the earliest semester in which each course can be completed. Separate the numbers with single spaces on one line. The first semester counts as semester 1.

Suppose there are 3 courses, course 1 is a prerequisite of course 2, and course 2 is a prerequisite of course 3. Then Minwook completes course 1 in semester 1, course 2 in semester 2, and course 3 in semester 3.