Line Up

N students want to stand in one line according to their height order. Since their exact heights cannot be measured directly, only the relative order of some pairs of students is known.

Given these comparison results, determine the range of positions each student can occupy in the line. Positions are numbered from 1 at the front to N at the back.

The first line contains N (1 ≤ N ≤ 256) and M (1 ≤ M ≤ 100,000), the number of height comparisons.

Each of the next M lines contains two student numbers A and B. This means student A must stand before student B. The same pair of students may have been compared more than once. A and B are never the same student.

Print N lines. On line i, print the earliest and latest positions where student i can stand.

If no valid line can satisfy all comparisons, print -1 on the first line.

In the provided visible case, students 1 and 2 have no fixed order between them, but both must stand before student 3. Therefore students 1 and 2 can each occupy positions 1 through 2, while student 3 can only occupy position 3.