Cơ sở hạ tầng Công nghệ của các Thợ mộc Cần cù được Giám sát (MITIT) bao gồm $N$ con hải ly được đánh số từ $1, \dots, N$. Có $M$ cặp hải ly $(u_i, v_i)$, trong đó ban đầu, hải ly $u_i$ chịu trách nhiệm giám sát hải ly $v_i$. Mỗi con hải ly đều được giám sát bởi ít nhất một con hải ly khác.

Busy Beaver, quản lý của MITIT, muốn cấu hình lại các mối quan hệ giám sát này. Trong một thao tác, anh ta có thể chọn một cặp $(u, v)$ trong đó hải ly $u$ hiện đang giám sát hải ly $v$ và thay đổi thành hải ly $v$ giám sát hải ly $u$. Tuy nhiên, anh ta phải đảm bảo rằng mọi con hải ly đều được giám sát bởi ít nhất một con hải ly khác tại mọi thời điểm.

Cấu hình cuối cùng mong muốn của Busy Beaver có thể được mô tả bằng một chuỗi $d$ có độ dài $M$, trong đó $d_i = 0$ nếu hải ly $u_i$ giám sát hải ly $v_i$ ở trạng thái cuối cùng và $d_i = 1$ nếu hải ly $v_i$ giám sát hải ly $u_i$ ở trạng thái cuối cùng. Hãy tìm một dãy thao tác ngắn nhất cần thiết để đạt được cấu hình cuối cùng này, hoặc thông báo rằng điều đó là không thể.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $T$ ($1 \le T \le 10^4$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa hai số nguyên $N$ và $M$ ($3 \le N \le M \le 10^5$).

Dòng thứ $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$). Không tồn tại $1 \le i < j \le M$ sao cho $(u_i, v_i) = (u_j, v_j)$ hoặc $(u_i, v_i) = (v_j, u_j)$.

Dòng tiếp theo chứa một chuỗi $d_1 \dots d_M$, trong đó $d_i \in \{0, 1\}$ với mọi $1 \le i \le M$.

Đảm bảo rằng trong cả cấu hình ban đầu và cấu hình cuối cùng, mỗi con hải ly đều được giám sát bởi ít nhất một con hải ly khác.

Đảm bảo rằng tổng $N$ trên tất cả các trường hợp thử nghiệm không vượt quá $10^5$.

Đảm bảo rằng tổng $M$ trên tất cả các trường hợp thử nghiệm không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi trường hợp thử nghiệm, nếu nhiệm vụ là không thể, hãy xuất ra một số nguyên duy nhất $-1$.

Nếu không, trước tiên hãy xuất ra một số nguyên $K$, số lượng thao tác được sử dụng. Trên dòng tiếp theo, xuất ra $K$ số nguyên $a_1, \dots, a_K$ ($1 \le a_i \le M$), biểu thị rằng giải pháp của bạn thực hiện các thao tác trên $(u_{a_i}, v_{a_i})$ theo thứ tự.

Nhiệm vụ con

Để đạt điểm tối đa, $K$ phải luôn là số lượng thao tác tối thiểu có thể. Nếu không, bạn sẽ nhận được $50\%$ số điểm cho mỗi nhiệm vụ con nếu bạn xuất ra chính xác bất kỳ dãy thao tác hợp lệ nào mà tổng $K$ trên tất cả các trường hợp thử nghiệm không vượt quá $10^6$.

• ($50$ điểm) $M \le 300$.
• ($50$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Ghi chú

Các thao tác trong trường hợp thử nghiệm đầu tiên được hiển thị bên dưới. Lưu ý rằng việc thực hiện các thao tác theo thứ tự ngược lại là không chấp nhận được vì hải ly $2$ phải được giám sát tại mọi thời điểm.

Trong trường hợp thử nghiệm thứ hai, không thể đạt được cấu hình cuối cùng.

Trong trường hợp thử nghiệm thứ ba, không cần thực hiện thao tác nào.