Một hệ thống đèn trang trí gồm ~n~ đèn được đánh số từ ~1~ đến ~n~ và ~n - 1~ đoạn dây nối điều khiển, mỗi đoạn nối một cặp hai đèn khác nhau. Hệ thống dây nối điểu khiển thỏa mãn tính chất sau đây: Không có đoạn dây nào nối một đèn với chính nó; không có hai đoạn dây nào nối cùng một cặp đèn và hơn nữa không tìm được dãy các đèn ~v_1, v_2, ..., v_k, v_1~, trong đó hai đèn liên tiếp là có đoạn dây nối và không có đoạn dây nối nào xuất hiện quá một lần.

Tại mỗi thời điểm, mỗi đèn sẽ sáng màu xanh hoặc đỏ. Bộ điều khiển hệ thống đèn có thể thực hiện tác động nhiều lần việc thay đổi trạng thái các đèn, mỗi lần tác động là thay đổi màu của một đèn nào đó và tất cả các đèn có dây nối với nó, cụ thể nếu đèn đang sáng màu xanh sẽ chuyển sang sáng màu đỏ, ngược lại nếu đèn đang sáng màu đỏ sẽ chuyển sang sáng màu xanh.

Cho biết trạng thái ban đầu về màu của ~n~ đèn và thông tin về các dây nối điều khiển, hãy tìm cách điều khiển để tất cả các đèn sáng màu xanh.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n, T~ (~n\le 3000~, ~T\le 500~) — số lượng đèn và số trường hợp thử nghiệm.

Mỗi dòng trong số ~n - 1~ dòng tiếp theo gồm hai số nguyên ~u, v~ (~1\le u, v\le n~, ~u\ne v~) — có đoạn dây nối giữa hai đèn ~u~ và ~v~.

Dòng thứ ~i~ trong số ~T~ dòng cuối cùng gồm ~n~ số nguyên ~c_{i,1}, c_{i,2}, ..., c_{i,m}~, trong đó ~c_{ij} = 1~ nếu đèn ~j~ sáng màu xanh và ~c_{ij} = 0~ nếu đèn ~j~ sáng màu đỏ trong thử nghiệm thứ ~i~.

Dữ liệu đảm bảo hệ thống dây nối điều khiển thoả mãn đề bài.

Output

Với mỗi thử nghiệm, in ra ~-1~ nếu không tồn tại cách điều khiển, ngược lại in ra trên một dòng:

• Số nguyên ~s~ (~s \leq n~) — số lần dùng bộ điều khiển.

• Tiếp theo là ~s~ số nguyên ~l_1, l_2, ..., l_s~ mô tả cách điều khiển, trong đó tác động thứ ~h~ (~1\le h\le s~) làm đảo màu của đèn ~l_k~ và các đèn nối với ~l_k~.

Scoring

Sample Input 1

4 1
1 2
2 3
3 4
0 1 1 0

Sample Output 1

2 2 3