VMCOMP - Công việc tuyển dụng

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Năm 2020, Raldono trở thành giám đốc nhân sự tại công ty IONV. Trong đợt tuyển nhân viên mới lần này, có N ứng viên, được đánh số từ 1 đến N, nộp hồ sơ đăng kí. Là một công ty hàng đầu với nhiều dự án lớn cần thực hiện, IONV luôn muốn các nhân viên của mình có kĩ năng làm việc nhóm hiệu quả nhất. Do đó, bên cạnh những yếu tố thông thường mà các nhà tuyển dụng hay quan tâm, Raldono sẽ ưu tiên cho những ứng viên đã từng có kinh nghiệm làm việc chung với các ứng viên khác. Theo tiêu chí này, Raldono đã tổng hợp được một danh sách M cặp ứng viên (u, v) đã từng làm việc với nhau và biết được độ hiệu quả của họ, kí hiệu là E(u, v) .

  • Độ hiệu quả của một ứng viên u được tính bằng tổng E(u, v) với điều kiện cả 2 ứng viên u và v cùng được tuyển.
  • Độ hiệu quả của công ty sau đợt tuyển nhân viên mới sẽ tăng một giá trị bằng với độ hiệu quả nhỏ nhất của một ứng viên được chọn.

Ban lãnh đạo công ty yêu cầu độ hiệu quả của công ty phải tăng không ít hơn S . Hãy giúp Raldono tìm số lượng ứng viên lớn nhất có thể được tuyển và in ra danh sách các ứng viên đó. Nếu có nhiều danh sách thỏa, in ra một danh sách bất kì. Nếu không có cách tuyển thỏa yêu cầu, in ra -1.

Input

  • Dòng 1 chứa 3 số nguyên N , M và S .
  • M dòng tiếp theo mỗi dòng chứa 3 số nguyên u , v và E(u, v) . Mỗi cặp số (u, v) chỉ xuất hiện tối đa 1 lần.

Output

  • Dòng 1 in ra số K tương ứng với số lượng ứng viên lớn nhất có thể được tuyển hoặc -1.
  • Nếu có cách tuyển thỏa yêu cầu, dòng 2 in ra K số tương ứng với các ứng viên được tuyển theo thứ tự tăng dần.

Giới hạn

  • 1 ≤ N, M, E(u, v) ≤ 100000
  • 1 ≤ u, v ≤ N
  • 1 ≤ S ≤ 10 9
  • Trong 20% số test, N ≤ 20
  • Trong 50% số test, N ≤ 1000

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 2 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input: 

4 4 15
1 2 10
2 3 20
2 4 5
3 4 8

Output: 

2
2 3

Input: 

3 2 7
1 2 3
1 3 1

Output: 

-1

  • Người up: voj
  • Nguồn bài: VM13 - Nguyễn Tấn Sỹ Nguyên