Miền Tây sông nước nổi tiếng với hệ thống kênh rạch chằng chịt và những khu chợ nổi sầm uất tạo thành hệ thống chợ xương rồng. Cụ thể, tại đây có khu chợ nổi (được đánh số từ đến ) và đoạn kênh rạch kết nối các chợ này. Hệ thống kênh rạch này có đặc điểm rất đặc biệt: mỗi đoạn kênh chỉ thuộc tối đa một chu trình đơn. Cấu trúc này tạo thành một hệ thống mà ta gọi là chợ xương rồng.
Mỗi đoạn kênh rạch này có thể giao thương đi lại theo cả hai chiều, tuy nhiên nó chỉ hoạt động đến thời điểm nước thủy triều rút xuống. Cụ thể, danh sách đoạn kênh rạch được liệt kê theo thứ tự thời gian thủy triều rút xuống: Đoạn kênh rạch thứ sẽ kết nối hai chợ , , và thủy triều rút tại thời điểm .
Với hai chợ , ta nói từ kịp thời đến được nếu tồn tại một cách đi từ chợ đến chợ qua các đoạn kênh rạch mà đoạn kệnh rạch sau có thời điểm thủy triều rút sau đoạn kênh rạch trước.
Yêu cầu: Với mỗi khu chợ (từ đến ), hãy đếm xem có bao nhiêu khu chợ khác mà từ có thể kịp thời đến được .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên () là số lượng khu chợ nổi và số lượng đoạn kênh rạch.
dòng tiếp theo mô tả các đoạn kênh rạch theo thứ tự thời điểm thủy triều rút. Dòng thứ chứa hai số nguyên () cho biết đoạn kênh rạch thứ nối giữa chợ và . Đảm bảo hệ thống kênh rạch nối các chợ là liên thông, không có đoạn kênh rạnh nào nối một chợ với chính nó, giữa hai khu chợ bất kỳ có tối đa một đoạn kênh rạnh nối trực tiếp, và cấu trúc mạng lưới thỏa mãn tính chất "xương rồng".
Kết quả: In ra số nguyên trên một dòng. Số thứ là số lượng khu chợ mà từ có thể kịp thời đến được .
Ví dụ:
Dữ liệu:
3 3
1 2
2 3
3 1
Kết quả:
2 2 2
Minh họa ví dụ 1
Dữ liệu:
5 4
1 2
2 3
3 4
4 5
Kết quả:
4 4 3 2 1
Minh họa ví dụ 2
Giới hạn:
Subtask #1: số điểm có ;
Subtask #2: số điểm khác có ;
Subtask #3: số điểm khác có ;
Subtask #4: số điểm khác có và đồ thị là một vòng tròn đơn;
Subtask #5: số điểm còn lại không có ràng buộc bổ sung.
