Đây là một bài toán chạy hai lần (run-twice communication).

Sau nhiều ngày yên bình ăn chuối, các Minion quyết định xây dựng một hệ thống giao chuối mới.

Có ~n~ trạm chuối, được đánh số từ ~1~ đến ~n~, và ~m~ đường hầm hai chiều giữa chúng. Các đường hầm tạo thành một đồ thị vô hướng đơn. Để tránh nhầm lẫn trong quá trình giao hàng, các Minion muốn tô màu cho mỗi trạm bằng một trong bốn màu, được đánh số từ ~1~ đến ~4~, sao cho bất kỳ hai trạm nào được nối bởi một đường hầm đều có màu khác nhau.

Kevin đã tìm được một cách tô màu hợp lệ cho toàn bộ bản đồ và đang rất háo hức để chia sẻ nó với Stuart. Tuy nhiên, Stuart đang ở phòng khác và không thể nhìn thấy cách tô màu của Kevin.

Để chia sẻ cách tô màu, Kevin chỉ được phép gửi cho Stuart một thông điệp rất ngắn: một mảng có độ dài không quá ~\lfloor n / 2 \rfloor~, trong đó mỗi phần tử phải là một số nguyên từ ~1~ đến ~4~.

Nhiệm vụ của bạn là viết một chương trình giúp cả hai Minion.

Chương trình sẽ được chạy hai lần:

• Ở lần chạy thứ nhất, chương trình của bạn đóng vai Kevin. Chương trình nhận vào đồ thị và một cách tô màu hợp lệ của đồ thị, và phải xuất ra thông điệp của Kevin.

• Ở lần chạy thứ hai, chương trình của bạn đóng vai Stuart. Chương trình nhận vào cùng đồ thị và thông điệp của Kevin, và phải xuất ra bất kỳ cách tô màu hợp lệ nào của đồ thị bằng các màu từ ~1~ đến ~4~. Lưu ý rằng cách tô màu của Stuart không nhất thiết phải giống với cách tô màu ban đầu của Kevin.

Input

Lần chạy thứ nhất

Dòng đầu tiên chứa chuỗi Kevin. Mục đích của điều này là để chương trình của bạn nhận ra đây là lần chạy đầu tiên, và nó nên hoạt động như Kevin.

Mỗi lần chạy chứa nhiều test case. Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 2 \cdot 10^5~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 3 \cdot 10^5~) — số lượng trạm chuối và đường hầm, tương ứng.

• Mỗi trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~), biểu thị một đường hầm giữa các trạm ~u_i~ và ~v_i~.

• Dòng cuối cùng chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 4~), trong đó ~a_i~ là màu của trạm ~i~ trong cách tô màu hợp lệ của Kevin.

Đảm bảo rằng cách tô màu đã cho là hợp lệ. Tức là, với mọi cạnh ~(u, v)~, ta có ~a_u \ne a_v~.

Lần chạy thứ hai

Dòng đầu tiên chứa chuỗi Stuart. Mục đích của điều này là để chương trình của bạn nhận ra đây là lần chạy thứ hai, và nó nên hoạt động như Stuart.

Mỗi lần chạy chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 2 \cdot 10^5~) — số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 3 \cdot 10^5~) — số lượng trạm chuối và đường hầm, tương ứng.

• Mỗi trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~), biểu thị một đường hầm giữa các trạm ~u_i~ và ~v_i~.

• Dòng tiếp theo chứa một số nguyên ~k~ (~0 \le k \le \lfloor n / 2 \rfloor~) — độ dài thông điệp của Kevin.

• Dòng tiếp theo chứa ~k~ số nguyên ~c_1, c_2, \ldots, c_k~ (~1 \le c_i \le 4~), biểu thị thông điệp của Kevin. Nếu ~k = 0~, dòng này để trống.

Đảm bảo rằng:

• Đồ thị không chứa khuyên và không có cạnh song song.

• Lần chạy thứ hai chứa đúng các bộ dữ liệu giống hệt lần chạy thứ nhất: cùng số lượng bộ dữ liệu, cùng các đồ thị, và cùng thứ tự các test case.

• Tổng ~n~ qua tất cả các test case không vượt quá ~2 \cdot 10^5~.

• Tổng ~m~ qua tất cả các test case không vượt quá ~3 \cdot 10^5~.

Output

Lần chạy thứ nhất

Với mỗi test case, hãy xuất thông điệp của Kevin theo định dạng sau:

• Trên dòng đầu tiên, xuất một số nguyên ~k~ (~0 \le k \le \lfloor n / 2 \rfloor~) — độ dài của thông điệp.

• Trên dòng thứ hai, xuất ~k~ số nguyên ~c_1, c_2, \ldots, c_k~ (~1 \le c_i \le 4~). Nếu ~k = 0~, dòng này có thể để trống.

Lần chạy thứ hai

Với mỗi test case, hãy xuất một dòng chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le 4~), trong đó ~b_i~ là màu mà Stuart gán cho trạm ~i~. Cách tô màu của Stuart phải hợp lệ. Nói cách khác, với mọi cạnh ~(u, v)~, phải có ~b_u \ne b_v~.

Interaction

Scoring

Tổng điểm của bài toán này là ~1750~.

Sample Input 1

Kevin
2
5 6
1 2
2 3
3 4
4 5
5 1
1 4
1 2 3 4 2
3 3
1 2
2 3
3 1
1 2 3

Sample Output 1

2
3 2
1
3

Sample Input 2

Stuart
2
5 6
1 2
2 3
3 4
4 5
5 1
1 4
2
3 2
3 3
1 2
2 3
3 1
1
3

Sample Output 2

4 3 2 1 3
1 2 3

Notes

Hai ví dụ tương ứng với hai lần chạy của cùng một chương trình. Lưu ý rằng ví dụ chỉ minh hoạ cách mà chương trình tương tác, không thể hiện cách mà đáp án đúng được suy luận ra.

Trong lần chạy đầu tiên, Kevin nhận được các đồ thị cùng với các cách tô màu hợp lệ. Anh ấy gửi các thông điệp ~(3, 2)~ cho đồ thị đầu tiên, và ~(3)~ cho đồ thị thứ hai.

Trong lần chạy thứ hai, Stuart nhận được cùng các đồ thị và các thông điệp do Kevin gửi, rồi xuất ra các cách tô màu ~(4,3,2,1,3)~ và ~(1,2,3)~ cho đồ thị thứ nhất và thứ hai, tương ứng.

Trong cả hai đồ thị, mọi cặp trạm kề nhau đều có màu khác nhau, nên các cách tô màu là hợp lệ. Lưu ý rằng các cách tô màu của Stuart không nhất thiết phải giống với các cách tô màu ban đầu của Kevin.