Đến Szeged, như thường lệ, ông Malnar buộc phải làm quen với văn hóa địa phương, từ đó thử tất cả các món ăn truyền thống, đặc sản ẩm thực và đồ uống địa phương.

Chúng ta có thể tưởng tượng Szeged là ~n~ địa điểm thú vị được đánh số từ ~1~ đến ~n~ được kết nối bởi ~n−1~ con đường hai chiều sao cho có một con đường sử dụng các con đường giữa mỗi cặp địa điểm thú vị. Điều ngạc nhiên là ông Malnar cần đúng một phút để đi bộ qua mỗi con đường. Thời gian dành cho việc đi bộ ở một địa điểm thú vị là không đáng kể.

Ông Malnar có một danh sách ~m~ nhà hàng mà ông muốn ghé thăm. Nó bao gồm ~m~ số nguyên dương trong đó số thứ ~i~ đại diện cho một địa điểm thú vị gần nhà hàng thứ ~i~.

Một vấn đề là ông Malnar phải ăn kem ở tiệm bánh ngọt ngay sau khi dùng bữa tại nhà hàng. Một vấn đề khác là ông ấy từ chối ghé thăm cùng một tiệm bánh ngọt hai lần.

May mắn thay, ông ấy đã chuẩn bị sẵn sàng vì ông ấy quen thuộc với ~m~ tiệm bánh ngọt có vị trí mà ông ấy nhớ trong một danh sách gồm ~m~ số nguyên dương trong đó số thứ ~i~ đại diện cho một địa điểm thú vị gần đó là cửa hàng bánh ngọt thứ ~i~.

Ông Malnar mệt mỏi sau chuyến đi và không muốn đi bộ nhiều hơn mức cần thiết, vì vậy ông ấy yêu cầu bạn tính xem ông ấy sẽ phải đi bộ bao nhiêu và đưa ra yêu cầu ghé thăm các nhà hàng và cửa hàng bánh ngọt, vì ông ấy có khả năng điều hướng giữa chúng mà không có sự trợ giúp.

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

Input

• Dòng đầu tiên gồm các số nguyên ~n~, ~m~ (~1 \leq m \leq n \leq 3 \times 10^5~) lần lượt là số địa điểm thú vị và số nhà hàng/tiệm bánh ngọt.
• Dòng thứ hai gồm ~m~ số nguyên ~a_i~ (~1 \leq a_i \leq n~, ~a_i \neq a_j~ với mọi ~i \neq j~) là danh sách nhà hàng.
• Dòng thứ ba gồm ~m~ số nguyên ~b_i~ (~1 \leq b_i \leq n~, ~b_i \neq b_j~ với mọi ~i \neq j~) là danh sách tiệm bánh ngọt.
• Mỗi dòng trong ~n-1~ dòng tiếp theo gồm hai số nguyên ~x_i~ và ~y_i~ (~1 \leq x_i, y_i \leq n~), có nghĩa là có đường đi giữa địa điểm thú vị ~x_i~ và ~y_i~.

Output

• Ở dòng đầu tiên đưa ra ~t~, thời gian tính bằng phút mà ông Malnar sẽ phải đi bộ để tham quan tất cả các nhà hàng và tiệm bánh ngọt, rồi quay về vị trí ~1~.

• Ở dòng thứ hai ghi ~2 \times m~ số nguyên ~v_i~, thứ tự ghé thăm các nhà hàng và tiệm bánh ngọt.

  Các số ở vị trí lẻ đại diện cho các nhà hàng và sẽ tạo thành hoán vị của ~m~ số nguyên dương đầu tiên. Các số ở vị trí chẵn đại diện cho các cửa hàng bánh ngọt và cũng phải tạo thành một hoán vị của ~m~ số nguyên dương đầu tiên.

  Việc ghé thăm các địa điểm theo thứ tự nhất định và quay lại vị trí ban đầu bằng cách đi con đường ngắn nhất giữa mỗi địa điểm sẽ mất đúng ~t~ phút.

  Nếu có nhiều thứ tự tối ưu, hãy xuất ra bất kỳ thứ tự nào.

Scoring

1. ~n \leq 5 \times 10^3, m \leq 10~ (20 điểm)

2. ~x_i = i, y_i = i + 1 \space \forall i=1,2,...,n-1~ (20 điểm)

3. ~n \leq 5 \times 10^3~ (30 điểm)

4. Không có ràng buộc gì thêm (40 điểm)

Sample Input 1

3 1
2
3
1 2
1 3

Sample Output 1

4
1 1

Sample Input 2

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

Sample Output 2

18
3 1 4 2 2 4 1 3

Sample Input 3

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

Sample Output 3

24
4 4 5 5 3 3 2 2 1 1