Tàu đồ chơi

Có một đoàn tàu đồ chơi chạy trên mạng lưới đường ray gồm $n$ nhà ga, đánh số từ $1$ đến $n$. Tại mỗi thời điểm đoàn tàu đứng ở đúng một nhà ga và di chuyển vòng tròn: sau ga $i$ (với $1\le i<n$) đoàn tàu tới ga $i+1$, còn sau ga $n$ thì quay lại ga $1$. Mỗi lần di chuyển sang ga kế tiếp mất đúng $1$ giây.

Có $m$ viên kẹo cần được giao. Viên kẹo thứ $i$ hiện đang ở ga $a_i$ và cần được đưa tới ga đích $b_i$ (với $a_i\ne b_i$).

Đoàn tàu có sức chứa vô hạn và tại một ga có thể dỡ xuống bao nhiêu viên kẹo tuỳ ý. Tuy nhiên, mỗi lần đoàn tàu rời khỏi một ga, nó chỉ có thể mang theo tối đa một viên kẹo được chất lên tại ga đó (bạn được tự chọn viên kẹo nào trong số các viên đang ở ga đó). Thời gian chất và dỡ kẹo được bỏ qua.

Với mỗi nhà ga, hãy tính thời gian nhỏ nhất mà đoàn tàu cần để giao hết tất cả các viên kẹo, nếu nó bắt đầu xuất phát từ ga đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số nhà ga và số viên kẹo.
• Trong $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$: ga xuất phát và ga đích của viên kẹo thứ $i$.

Dữ liệu ra

In ra một dòng gồm $n$ số nguyên cách nhau bởi dấu cách. Số thứ $i$ là thời gian nhỏ nhất (tính bằng giây) mà đoàn tàu cần để giao hết mọi viên kẹo nếu xuất phát từ ga $i$.

Ràng buộc

• $2\le n\le 100$
• $1\le m\le 200$
• $1\le a_i,b_i\le n$ và $a_i\ne b_i$

Ví dụ