Khu du lịch sinh thái có điểm tham quan đánh số từ đến . Có lối mòn nối các điểm này với nhau thành một mạng lưới du lịch, cho phép khách từ một điểm, theo các lối mòn có thể tới điểm tham quan bất kỳ khác từ nơi mình đang đứng. Đường thứ có độ dài , nối hai điểm và .
Để nâng cấp chất lượng phục vụ người ta quyết định lát đá một số lối đi sao cho từ một điểm tham quan có thể tới được điểm khác bằng đường đã lát đá. Số phiến đá khai thác được là tấm, mỗi tấm có độ dài đơn vị. Như vậy để lát đoạn đường độ dài cần đúng tấm. Theo các lối này du khách chỉ có thể đi bộ. Ban Quản lý khu sinh thái muốn có thêm một số đường rộng có thể chạy minibus. Mỗi đường rộng cần số đá gấp lần so với lát cho đường bộ. Mọi người muốn có được số đường rộng càng nhiều càng tốt nhưng vẫn phải đảm bảo từ một điểm tham quan có thể tới được điểm khác bằng đường đã lát.
Hãy xác định một cách lát đường thỏa mãn các yêu cầu đã nêu. Nếu không có cách lát thì đưa ra thông báo Impossible.
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên và ;
Dòng thứ trong dòng sau chứa ba số nguyên và . Không có đoạn đường nào có hai điểm đầu và cuối trùng nhau, giữa hai điểm khác nhau có không quá một đoạn đường nối trực tiếp. Các đường được đánh số từ đến theo trình tự nhập.
Kết quả:
Nếu không có cách lát thì đưa ra thông báo Impossible. Nếu có cách lát thì dòng đầu tiên đưa ra hai số nguyên và – số đường thường và đường rộng. Dòng thứ hai đưa ra số nguyên – các đường lát thường, dòng thứ ba đưa ra số nguyên – các đường lát rộng.
Ví dụ:
Dữ liệu:
4 4 10 2
1 2 3
3 4 5
1 3 1
3 2 1
Kết quả:
1 2
2
3 4
Ghi chú: Nếu chỉ trả lời đúng được dòng thứ nhất thì được số điểm của test.
