Cho một đồ thị có hướng không chu trình (DAG) gồm \(n\) đỉnh \(m\) cạnh. Đồ thị không có khuyên hay nhiều cạnh nối cùng một cặp đỉnh, tuy nhiên có thể không liên thông.
Nhiệm vụ của bạn trong bài này là gán giá trị cho các đỉnh (từ đây gọi giá trị của đỉnh \(i\) là \(A_i\)) trong đồ thị sao cho:

• Các giá trị này tạo thành một hoán vị có độ dài \(n\) (mỗi số từ 1 đến \(n\) xuất hiện đúng một lần trong dãy).
• Nếu tồn tại một cạnh có hướng nối từ \(u\) tới \(v\) thì \(A_u<A_v\).
• Nếu tồn tại nhiều cách sắp xếp thì chọn dãy A có thứ tự từ điển là nhỏ nhất.

Yêu cầu: Hãy tìm dãy giá trị thỏa mãn tất cả điều kiện trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1≤n,m≤10^5\));
• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u_i\) và \(v_i\ (1≤u_i,v_i≤n)\), cho biết có cạnh có hướng nối từ \(u_i\) đến \(v_i\). Dữ liệu đảm bảo giữa hai đỉnh bất kỳ không có nhiều hơn một cạnh nối và đồ thị đã cho không có chu trình.

Output

• Ghi ra \(n\) số nguyên từ 1 đến \(n\) là hoán vị nhỏ nhất có thể tìm được.

Scoring

• 30% số điểm tương ứng với 30% số test có \(n ≤ 8\);
• 30% số điểm tương ứng với 30% số test có \(n ≤ 2000\);
• 40% số điểm không có ràng buộc gì thêm.

Example

3 3
1 2
1 3
3 2

1 3 2

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

4 1 2 3