6. LQDOJ Contest #15 - Bài 6 - Nhiều Đường Đi Nhất
, một thanh niên hướng nội đã cùng với crush của mình có một buổi đêm giao thừa đầy vui vẻ trong thành phố LQDOJ. Thành phố LQDOJ là một thành phố rộng lớn, có \(N\) giao lộ được đánh số từ \(1\) đến \(N\) và có \(M\) con đường được đánh số từ \(1\) đến \(M\). Mỗi con đường nối liền một cặp giao lộ khác nhau, và không có cặp giao lộ nào được kết nối bởi nhiều hơn một con đường. Từ bất kỳ giao lộ nào, và crush của mình đều có thể đi đến bất kỳ giao lộ khác thông qua các con đường đã cho.
và crush của mình đã cùng nhau khám phá từng ngõ ngách trong thành phố. Tuy nhiên, đã lỡ làm đổ cây kem vào áo của crush khi đang ăn dở cây kem của mình. Điều đó làm crush của giận và bỏ đi trong sự hoảng hốt của . muốn đi tìm crush của mình nhưng anh ấy lại không biết hiện tại cô ấy đang ở đâu, tuy nhiên anh ấy nhận ra rằng mình cùng với cô ấy chắc chắn đã đi qua mọi ngóc ngách trong thành phố, điều này có nghĩa là cùng crush của mình đã đi qua tất cả \(M\) con đường ít nhất một lần, nên chắc chắn rằng crush của mình phải ở đâu đó trong \(M\) con đường ấy.
May mắn thay, có dẫn theo chú chó theo trong suốt đêm ấy. Và chú chó ấy có khả năng ghi nhớ rằng con đường thứ \(i\) nối giữa giao lộ \(a_i\) và \(b_i\) đã được đi qua tại thời điểm \(c_i\) (và chú chó ấy có khả năng đánh hơi crush của anh ấy rất tốt). Tuy nhiên khả năng ghi nhớ của lại bị rối loạn khiến thứ tự các con đường mà nó đã đi qua được ghi nhớ lại một cách hỗn loạn và đôi khi không đúng logic. Ví dụ, nhớ là đã đi qua một con đường tại thời điểm \(10\), nhưng chú chó ấy lại không nhớ mình đã đi qua con đường nào ở thời điểm \(9\).
Người ta có câu "chủ nào, chó nấy". cũng bị trường hợp giống như chú chó của mình 🤡
Tuy trí nhớ rối loạn nhưng là một người thông minh, anh ấy nghĩ ra một kế sách là đi lại từ đầu để nhớ lại hành trình đêm qua mình đã đi những đâu và nhờ đánh hơi để tìm crush. bắt đầu cuộc hành trình của mình ở giao lộ \(1\). Vì không muốn lạc đường, sẽ đi qua các con đường theo thứ tự mà thời điểm của con đường tiếp theo phải lớn hơn thời điểm của con đường trước đó (theo trí nhớ của ). Nói cách khác, nếu đang đi qua một con đường có thời điểm \(c_{current}\), thì thì con đường tiếp theo anh chọn phải có thời điểm \(c_{next} > c_{current}\). Lưu ý rằng anh có thể đi qua một giao lộ nhiều lần.
cần chuyến đi tìm kiếm crush này sẽ có nhiều con đường càng tốt, điều đó giúp tăng tỉ lệ tìm thấy crush của mình hơn nhờ vào việc có thể đánh hơi được nhiều hơn. Do đó cần biết số lượng con đường lớn nhất đến từng giao lộ tuân theo quy tắc được nêu trên. Nhưng việc tính toán quá phức tạp, không thể tính nhẩm. Và cũng không mang laptop hay máy tính theo để tính toán số lượng con đường lớn nhất mà anh ấy có thể đi qua từ giao lộ \(1\) tới từng giao lộ khác. Với tư cách là một người có tài năng về code, Bạn hãy giúp giải quyết bài toán trên.
Input
- Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((2 \le N \le 10^5,1 \le M \le 10^6)\).
- \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương lần lượt là \(a_i\), \(b_i\), \(c_i\) \((1 \le a_i,b_i \le N, 1 \le c_i \le 10^9)\).
- Dữ liệu vào luôn đảm bảo rằng \(a_i \neq b_i\) với mọi \(i\).
Output
- In ra \(N\) số nguyên, mỗi số cách nhau một khoảng trắng gồm số con đường lớn nhất mà anh ấy có thể đi qua từ giao lộ \(1\) tới từng giao lộ khác. Nếu không thể đi đến một giao lộ nào đó thì in ra \(0\) để biểu thị rằng không có đường đi nào khả thi đến giao lộ đó.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\) và \(M \le 15\).
- Subtask \(2\) (\(20\%\) số điểm): Có \(N \le 10^5\) và \(M = N - 1\).
- Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 10^3\) và \(M \le 10^4\).
- Subtask \(4\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 3 \times 10^5\) và \(c_i \neq c_j\) với mọi \(i \neq j\).
- Subtask \(5\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 3 \times 10^5\).
- Subtask \(6\) (\(10\%\) số điểm): Có \(N \le 10^5\) và \(M \le 10^6\) và \(c_i \neq c_j\) với mọi \(i \neq j\).
- Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm
Example
Test 1
Input
8 12
1 4 9
1 6 4
1 5 1
3 4 11
3 5 10
5 6 2
6 2 6
2 8 7
5 8 8
7 8 5
5 7 14
3 7 12Output
3 3 6 7 8 2 7 4Note
- Đây là ví dụ minh họa về giao lộ và các đường phố:
- Đây là ví dụ hành trình tối ưu theo quy tắc thời điểm trên đề bài để đến giao lộ \(3\), đi qua nhiều con đường nhất: \(1\overset{1}{-}5\overset{2}{-}6\overset{6}{-}2\overset{7}{-}8\overset{8}{-}5\overset{10}{-}3.\)
- Lưu ý rằng khi đi ở giao lộ số \(8\) ta không thể tiếp tục đi qua giao lộ số \(7\) vì thời điểm của đường đó là \(5\) nhưng đã đến từ đường giao lộ số \(8\) từ thời điểm \(7\).