Lottery (lottery.*)

Cuội càng ngày càng trở nên nghiện Vietlott, một trò chơi xổ số may rủi đã xuất hiện tại Viêt Nam được vài năm nay. Trò xổ số diễn ra như sau:

• Cuội sẽ đến văn phòng xổ số gần nhất của Vietlott và chọn loại giải mình sẽ tham gia, mỗi loại giải của Vietlott tương ứng với độ dài của dãy số trên tờ vé số Cuội sẽ mua. Cuội có thể mua nhiều tờ vé số tùy ý.

• Vào cuối ngày, công ty Vietlott, với mỗi loại giải công ty sẽ quay số để tìm ra một dãy số may mắn ứng với từng loại giải.

Tất nhiên, Cuội sẽ giành được giải đặc biệt nếu một trong những tờ vé số anh ấy đã mua có dãy số trùng với dãy số may mắn ứng với loại giải của tờ vé số đó mà công ty Vietlott quay ra. Bạn của Cuội là Bờm làm trong công ty Vietlott đã quyết định giúp cậu bằng cách nói cho cậu biết một số đặc điểm của một dãy số may mắn:

• Dãy số chỉ bao gồm các số tự nhiên từ khoảng \(\lbrack 1,\ n\rbrack\)

• Tất cả các số trong dãy số là phân biệt.

• Hai số liên tiếp trong dãy đều nằm trong danh sách các cặp số được phép đứng cạnh nhau trong dãy. Danh sách các cặp số được phép đứng cạnh nhau có đặc điểm sau:

  • Là một tập các cặp số khác nhau trong khoảng \(\lbrack 1,\ n\rbrack\).

  • Và nếu ta coi mỗi cặp số là một cạnh của một đồ thị, thì đồ thị tạo bởi tập các cặp số được phép đứng cạnh nhau là một đồ thị không có cạnh nào nằm trong nhiều hơn một chu trình đơn.

Bờm đã đưa cho Cuội một danh sách các cặp số được phép đứng cạnh nhau và Cuội quyết định ngày mai, Cuội sẽ mua số lượng vé bằng tất cả các dãy may mắn có thể xuất hiện của một loại giải để chắc chắn giành được giải thưởng. Nhưng trước đó, anh ấy cần biết loại giải nào sẽ giúp anh ấy có lợi nhất, để biết được điều này anh ấy cần tính toán với mỗi loại giải sẽ có bao nhiêu dãy số may mắn có thể quay ra tương ứng với loại giải đó. Sẽ có đúng \(n\ \)loại giải tương ứng với độ dài từ 1 đến \(n\) của dãy số may mắn. Đây không phải một điều dễ dàng đối với Cuội, nên anh ấy muốn nhờ các bạn tính hộ anh ấy xem ứng với mỗi độ dài \(l\) trong khoảng từ 1 đến \(n\) có tất cả bao nhiêu dãy số may mắn có độ dài là \(l\).

Yêu cầu: với giá trị \(l\) từ 1 đến \(n\) đếm xem có bao nhiêu dãy số may mắn có độ dài đúng bằng \(l\).

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\ \)(\(1 \leq n \leq 4000,\ 0 \leq m \leq 10^{5}\))

• \(m\ \)dòng tiếp theo mỗi dòng mô tả một cặp số có thể đứng cạnh nhau. Dữ liệu đảm bảo không có cặp số nào xuất hiện quá một lần trong dữ liệu.

Kết quả: Ghi trên một dòng gồm \(n\ \)số nguyên \(s_{i}\), số thứ \(i\) là kết quả số dãy may mắn có độ dài \(i\) lấy phần dư cho \(10^{9} + 7\).

Ví dụ:

Input	Output		Input	Output
3 2 1 2 2 3	3 4 2		3 3 1 3 2 3 1 2	3 6 6

Giải thích: Với ví dụ đầu tiên các dãy may mắn có thể có độ dài 1 là (1), (2), (3); độ dài 2 là (1, 2), (2, 3), (2, 1) và (3, 2); độ dài 3 là (1, 2, 3) và (3, 2, 1).

Ràng buộc:

• Có 25% số điểm có \(n \leq 10\)

• Có 25% số điểm đồ thị trong dữ liệu sẽ có dạng không có chu trình

• Có 25% số điểm đồ thị trong dữ liệu có dạng mỗi đỉnh thuộc không quá một chu trình đơn.

• Có 25% số điểm còn lại không có ràng buộc gì thêm.