DP trên DAG: Đường đi Dài nhất và Đếm số Đường đi

Mô tả bài toán

Cho một đồ thị có hướng không có chu trình (DAG) gồm N đỉnh và M cạnh. Đỉnh xuất phát là 1 và đỉnh kết thúc là N. Hãy tính:

• Độ dài đường đi dài nhất từ 1 đến N (tính theo số cạnh). Nếu không có đường đi từ 1 đến N, in ra -1.
• Số lượng đường đi khác nhau từ 1 đến N modulo 10⁹ + 7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

• Dòng đầu tiên gồm 2 số nguyên N, M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000).
• M dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v mô tả cạnh có hướng từ u đến v (1 ≤ u, v ≤ N).

Output

• In ra hai số nguyên cách nhau bởi dấu cách: độ dài đường đi dài nhất và số lượng đường đi modulo 10⁹ + 7. Nếu không tới được N, in ra -1 0.

Ràng buộc

• Thời gian: 1.0s. Bộ nhớ: 256MB.

Ví dụ 1