Bạn là phóng viên phụ trách thể thao của tòa soạn JOI. Một giải bóng đá vòng tròn giữa \(n\) đội ở Croatia vừa kết thúc hôm qua; mỗi cặp đội đã thi đấu với nhau. Ban tổ chức đã xếp các đội từ hạng \(1\) đến hạng \(n\) dựa trên kết quả thi đấu và điều lệ giải.

Bạn chỉ được biết kết quả thắng thua của một số trận đấu, cùng các thông tin sau:

1. Không có trận hòa.
2. Mỗi đội có một thứ hạng khác nhau.
3. Với mọi \(1 \le a < b \le n\), trong trận đấu giữa đội hạng \(a\) và đội hạng \(b\), đội hạng \(a\) luôn thắng.

Để viết bài báo, bạn phải suy đoán bảng xếp hạng từ những thông tin này. Một bảng xếp hạng là thứ tự các đội từ hạng \(1\) đến hạng \(n\).

Yêu cầu

Xuất một bảng xếp hạng phù hợp với tất cả thông tin được cho. Đồng thời, xác định xem có bảng xếp hạng phù hợp nào khác với bảng bạn xuất ra hay không.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(n\). Các đội được đánh số từ \(1\) đến \(n\).
• Dòng thứ hai chứa số nguyên \(m\), là số trận đấu đã biết kết quả.
• Dòng thứ \(i+2\) (\(1 \le i \le m\)) chứa hai số nguyên \(x_i,y_i\) cách nhau bởi một dấu cách, cho biết đội \(x_i\) đã thắng đội \(y_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(n+1\) dòng:

• Dòng thứ \(i\) (\(1 \le i \le n\)) chứa số hiệu đội xếp hạng \(i\) trong một bảng xếp hạng phù hợp.
• Dòng thứ \(n+1\) chứa \(0\) nếu không có bảng xếp hạng phù hợp nào khác, hoặc \(1\) nếu có ít nhất một bảng xếp hạng phù hợp khác.

Nếu có nhiều bảng xếp hạng phù hợp, bạn được phép xuất bất kỳ bảng nào trong số đó.

Ràng buộc

• \(1 \le n \le 5\,000\).
• \(1 \le m \le 100\,000\).
• Các số hiệu đội trong kết quả thi đấu nằm trong đoạn từ \(1\) đến \(n\); hai đội trong một trận là khác nhau.
• Dữ liệu phù hợp với các thông tin đã nêu; luôn tồn tại ít nhất một bảng xếp hạng hợp lệ.

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(10\) test, mỗi test \(2\) điểm. Có \(30\%\) số điểm ứng với \(n \le 7\), \(m \le 15\) và tổng cộng \(60\%\) số điểm ứng với \(n \le 100\), \(m \le 2\,000\).

1. Nhóm 1 (\(6\) điểm, \(30\%\)): \(1 \le n \le 7\), \(1 \le m \le 15\).
2. Nhóm 2 (\(6\) điểm, \(30\%\)): \(1 \le n \le 100\), \(1 \le m \le 2\,000\).
3. Nhóm 3 (\(8\) điểm, \(40\%\)): \(1 \le n \le 5\,000\), \(1 \le m \le 100\,000\).

Ví dụ

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

3
4
1
2
0

3
2
2 1
2 3

2
1
3
1

2
3
1
1