#1447. ROADS - Đường hoa

Bản đồ giao thông của một thành phố có địa điểm đánh số từ tới và con đường hai chiều nối giữa các địa điểm đó. Những con đường được đánh số từ tới , con đường thứ nối giữa hai địa điểm và trên con đường này trồng loại hoa . ( có thể trùng nhau).

Một khách du lịch muốn đi từ địa điểm tới địa điểm theo một hành trình thỏa mãn điều kiện: Hai con đường liên tiếp trên đường đi phải trồng hai loại hoa khác nhau. Hãy tìm một hành trình như vậy.

Dữ liệu vào:

• Dòng đầu chứa bốn số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên dương .

Dữ liệu ra:

• Dòng đầu ghi số các con đường đi qua trên hành trình, nếu không tồn tại hành trình ghi số ;
• Nếu tồn tại hành trình, dòng thứ hai ghi số hiệu các con đường đi qua trên hành trình tìm được theo đúng thứ tự.

Các số trên một dòng được/phải ghi cách nhau bởi dấu cách.

Dữ liệu vào:

8 12 1 8
1 2 1
1 3 3
2 3 3
3 1 3
3 5 3
3 7 3
4 6 1
6 2 3
6 8 3
7 8 1
7 6 2
4 2 2

Dữ liệu ra:

5
1 12 7 11 10

Dữ liệu vào:

3 3 1 3
1 2 1
2 2 2
2 3 1

Dữ liệu ra:

3
1 2 3