Một đồ thị có hướng bao gồm n nút và m cạnh. Các nút được đánh số 1,2,...,n.

Tính toán cho mỗi nút số lượng nút bạn có thể đến được từ nút đó (bao gồm cả chính nút đó).

Input

Dòng đầu tiên chứa hai số nguyên n và m: số nút và số cạnh.

Khi đó có m dòng mô tả các cạnh. Mỗi dòng có hai số nguyên u và v riêng biệt: có một cạnh một chiều từ nút u đến nút v.

Output

In ra n số nguyên: với mỗi nút là số lượng nút có thể truy cập được.

Hạn chế

~1 \le n \le 5 \cdot 10^4~

~1 \le m \le 10^5~

Examples

Input

5 6
1 2
1 3
1 4
2 3
3 5
4 5

Output

5 3 2 2 1

​