Họa Hóc
Xem dạng PDF
NKN99 là một học sinh đang học về môn hóa. Trong môn hóa, bạn đang học về liên kết ion, liên kết cộng hóa trị và liên hết hydro. Để dễ hình dung thì bạn được giáo viên cho phát một mô hình nguyên tử của các chất. Chất bạn đang có trên tay gồm ~N~ nguyên tử và ~M~ liên kết. Bạn ấy khá phá nên bạn ấy muốn bỏ nhiều liên kết nhất để mô hình còn đủ ~N~ phân tử hóa học liên kết với nhau. Dù vậy, mỗi liên kết có một độ khó để loại bỏ khác nhau. Dù vậy, cũng như khá lười, tổng độ khó các cạnh bạn ấy loại bỏ không được quá ~S~. Bạn hãy giúp bạn NKN99 phá mô hình của giáo viên nhé.
Input
Dòng đầu gồm 3 số ~N,M,S(1\le N\le50000,1\le M\le 100000,1\le S\le10^{18})~
~M~ dòng tiếp theo, mỗi dòng gồm ~3~ số là ~U,V,C~ có nghĩa là có liên kết giữa nguyên tử ~U~ và nguyên tử ~V~ với độ khó để loại bỏ là ~C(1\le C\le10^9)~. Mô hình đảm bảo không có hai liên kết nào cùng nối vào một cặp nguyên tố giống nhau và các liên kết ban đầu tạo thành một đồ thị liên thông.
Output
Dòng đầu gồm ~1~ số là số liên kết nhiều nhất có thể loại bỏ.
Dòng thứ hai gồm một vài số là chỉ số cạnh được loại bỏ theo thứ tự tăng dần.
Nếu có nhiều cách in ra cách bất kỳ.
Sample Input 1
6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
Sample Output 1
2
1 6
Sample Input 2
6 10 20
4 3 4
2 4 2
1 4 3
6 3 2
5 1 5
5 2 3
3 5 2
4 6 4
6 5 3
6 2 4
Sample Output 2
5
2 3 4 6 7
Bình luận
solve:
đề làm khó e quá, đề kêu in chỉ số nhưng test thì in ra vị trí :(()