Lưu ý: testcase bài này vẫn còn khá yếu.

Một cây táo được biểu diễn bằng một đồ thị dạng cây. Đồ thị liên thông có ~N~ đỉnh và ~N - 1~ cạnh, trong đó đỉnh thứ ~i~ (~1 \le i \le N~) có trọng số là số nguyên dương ~w_i~ biểu diễn có một quả táo ở vị trí đó với khối lượng là ~w_i~ (gram). Alice chỉ có thể mang được không quá ~S~ gram nên cô muốn chọn hái một số quả táo thỏa mãn:

1) Tổng khối lượng các quả chọn hái là không quá ~S~.

2) Hai quả được chọn hái không kề nhau.

Yêu cầu: Hãy chọn hái các quả để tổng khối lượng các quả càng lớn càng tốt.

Dữ liệu: Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương ~N, S~ (~N \le 1000; S \le 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~w_1, w_2, \dots, w_N~ (~w_i \le 10^9~).
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le N~) mô tả các cạnh của cây. Dữ liệu đảm bảo luôn tồn tại cách chọn để đạt được tổng bằng ~S~.

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) theo khuôn dạng:

• Dòng đầu ghi số nguyên ~K~ là số quả chọn hái.
• Dòng thứ hai chứa ~K~ số chỉ số các quả chọn hái.

Giới hạn

• Subtask 1 (20%): ~N \le 40~; ~S \le 10^4~ và cây có dạng đường thẳng.
• Subtask 2 (20%): ~N \le 40~; ~S \le 10^4~.
• Subtask 3 (20%): ~S \le 10^6~ và cây có dạng đường thẳng.
• Subtask 4 (30%): ~S \le 10^6~.
• Subtask 5 (10%): Không có ràng buộc nào thêm.

Cách chấm điểm

Đây là bài toán chấm điểm theo tỉ lệ tối ưu. Gọi tổng khối lượng các quả táo chọn hái do thí sinh tìm được là ~P~, khi đó phần trăm số điểm đạt được cho mỗi test là ~\frac{P}{S} \times 100\%~.

Ví dụ

Input

5 10
3 7 2 8 5
1 2
2 3
3 4
4 5

Output

3
1 3 5

Giải thích: Chọn hái quả 1, 3 và quả 5, tổng khối lượng là ~3 + 2 + 5 = 10~. ```