#772. Đếm đường đi ngắn nhất (SHORTEST)

Cho một đồ thị vô hướng không trọng số gồm đỉnh và cạnh, các đỉnh được đánh số từ . Hỏi từ đỉnh , có bao nhiêu đường đi ngắn nhất đến mỗi đỉnh còn lại.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên dương , là số đỉnh và số cạnh của đồ thị.
• dòng tiếp theo, mỗi dòng gồm hai số nguyên dương , biểu thị có một cạnh nối đỉnh với đỉnh . Chú ý rằng có thể có khuyên (cạnh nối chính nó) và đa cạnh (nhiều cạnh nối cùng một cặp đỉnh).

Kết quả:

• Xuất ra dòng, mỗi dòng một số nguyên không âm. Dòng thứ xuất ra số lượng đường đi ngắn nhất khác nhau từ đỉnh đến đỉnh . Vì đáp án có thể rất lớn, bạn chỉ cần xuất kết quả sau khi . Nếu không thể đến được đỉnh , xuất ra .

Ví dụ:

Dữ liệu:

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

Kết quả:

1
1
1
2
4

Giới hạn:

• Với dữ liệu, ;
• Với dữ liệu, ;
• Với dữ liệu, .