Đến Szeged, ông Malnar như thường lệ có nghĩa vụ tìm hiểu văn hóa địa phương, và vì thế phải thử tất cả các món ăn truyền thống, các đặc sản và đồ uống địa phương.

Ta có thể hình dung Szeged gồm ~n~ địa điểm thú vị được đánh số từ ~1~ đến ~n~, nối với nhau bởi ~n - 1~ con đường hai chiều sao cho giữa mọi cặp địa điểm đều có một đường đi. Điều đáng ngạc nhiên là ông Malnar mất đúng một phút để đi hết mỗi con đường. Thời gian ở lại trong một địa điểm là không đáng kể.

Ông Malnar có danh sách ~m~ nhà hàng muốn ghé. Danh sách gồm ~m~ số nguyên dương, số thứ ~i~ là địa điểm mà gần đó có nhà hàng thứ ~i~.

Vấn đề là ông Malnar phải ăn kem ở một quán kem ngay sau khi ăn ở một nhà hàng. Một vấn đề khác là ông không chịu ghé cùng một quán kem hai lần.

May thay ông đã chuẩn bị trước: ông biết ~m~ quán kem, vị trí của chúng được cho bởi một danh sách ~m~ số nguyên dương, số thứ ~i~ là địa điểm mà gần đó có quán kem thứ ~i~.

Ông Malnar đã mệt sau chuyến đi và không muốn đi bộ nhiều hơn mức cần thiết, nên ông nhờ bạn tính xem ông sẽ phải đi bộ bao nhiêu, và cho biết thứ tự ghé các nhà hàng và quán kem.

Ông Malnar hiện đang ở địa điểm số ~1~ và phải quay lại đó khi kết thúc chuyến đi bộ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số địa điểm thú vị và số nhà hàng/quán kem.
• Dòng thứ hai chứa ~m~ số nguyên ~a_i~ — danh sách các nhà hàng.
• Dòng thứ ba chứa ~m~ số nguyên ~b_i~ — danh sách các quán kem.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~ — có một con đường giữa hai địa điểm ~x_i~ và ~y_i~.

Kết quả

• Dòng đầu tiên in ra ~t~ — số phút ông Malnar phải đi bộ để ghé hết các nhà hàng và quán kem, rồi quay lại địa điểm ~1~.
• Dòng thứ hai in ra ~2m~ số nguyên ~v_i~ — thứ tự ghé các nhà hàng và quán kem.

Các số ở vị trí lẻ là chỉ số nhà hàng và phải tạo thành một phép hoán vị của ~1..m~. Các số ở vị trí chẵn là chỉ số quán kem và cũng phải tạo thành một phép hoán vị của ~1..m~.

Việc ghé các địa điểm theo thứ tự đã cho rồi quay về vị trí xuất phát, luôn đi theo đường ngắn nhất giữa hai điểm liên tiếp, phải mất đúng ~t~ phút.

Nếu có nhiều thứ tự tối ưu, in ra một thứ tự bất kỳ.

Ví dụ

Đầu vào:

3 1
2
3
1 2
1 3

Đầu ra:

4
1 1

Giải thích: Ông Malnar trước tiên đi ~1~ phút tới nhà hàng duy nhất ở địa điểm ~2~, rồi ~2~ phút tới quán kem duy nhất ở địa điểm ~3~, và cuối cùng ~1~ phút để về địa điểm ~1~. Tổng cộng ông đi ~1 + 2 + 1 = 4~ phút.

Giới hạn

• ~1 \le m \le n \le 3 \cdot 10^5~
• ~1 \le a_i \le n~, ~a_i \ne a_j~ với mọi ~i \ne j~
• ~1 \le b_i \le n~, ~b_i \ne b_j~ với mọi ~i \ne j~
• ~1 \le x_i, y_i \le n~

Điểm của một subtask bằng điểm nhỏ nhất đạt được trên một test nào đó thuộc subtask đó.