Bật đèn

Trong tòa nhà trung tâm hội nghị Bitland có $N$ phòng họp (đánh số từ $1$ đến $N$) và $M$ hành lang nối các phòng đó. Biết rằng:

• Mỗi hành lang nối hai phòng khác nhau.
• Giữa hai phòng bất kỳ, tối đa chỉ có một hành lang.
• Từ bất kỳ phòng nào cũng có thể đi tới bất kỳ phòng khác thông qua các hành lang.

Vào buổi sáng, hệ thống đèn trong một số phòng có thể đang bật, trong khi ở những phòng khác thì không. Nhiệm vụ của bạn là bật đèn trong tất cả các phòng vào đầu ngày làm việc.

Tuy nhiên, toàn bộ đèn của mỗi phòng họp chỉ dùng chung một công tắc cảm biến rất kỳ lạ. Mỗi lần bạn bước vào một phòng, nếu toàn bộ đèn trong phòng đang bật thì công tắc sẽ tự động tắt hết đèn; nếu toàn bộ đèn đang tắt thì công tắc sẽ tự động bật hết đèn.

Cửa vào tòa nhà là ở phòng số $1$, vì vậy bạn bắt đầu bằng cách bước vào phòng $1$ và đi theo một hành trình theo thứ tự đến các phòng, mỗi phòng nào đó bạn có thể vào nhiều hơn một lần, cũng có phòng bạn có thể không vào lần nào. Bạn có thể kết thúc hành trình ở bất kỳ phòng nào. Vì sắp đến giờ làm việc, bạn phải đảm bảo rằng tất cả các phòng đều có đèn bật.

Yêu cầu: Bạn hãy tìm một hành trình đi đến các phòng họp sao cho tất cả các phòng đều có đèn được bật và thỏa mãn điều kiện tổng số lần đến các phòng không được vượt quá $5\times {10}^5$.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $N$ và $M$ ($2\le N\le {10}^5$, $1\le M\le {10}^5$), theo thứ tự là số phòng và số hành lang;
• Dòng thứ hai gồm $N$ số nguyên, mỗi số là $0$ hoặc $1$. Số thứ $i$ là $1$ nếu đèn trong phòng $i$ đang bật, là $0$ nếu đèn đang tắt. Biết rằng ít nhất một phòng có đèn đang tắt;
• $M$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $U_i$ và $V_i$ ($1\le U_i<V_i\le N$), biểu thị có một hành lang nối giữa phòng $U_i$ và $V_i$.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng đầu tiên ghi một số nguyên $K$ là số lượt đi vào các phòng trong hành trình. Số này không cần nhỏ nhất, nhưng phải không lớn hơn $5\times {10}^5$.
• Dòng thứ hai ghi $K$ số nguyên là thứ tự các phòng bạn bước vào (bắt đầu từ phòng $1$), sao cho sau khi kết thúc, tất cả các phòng đều có đèn được bật.

Hai phòng liên tiếp trong hành trình phải được nối trực tiếp bằng một hành lang. Lần bước vào phòng $1$ ở đầu hành trình cũng làm đổi trạng thái đèn phòng $1$.

Nếu có nhiều đáp án thỏa mãn, bạn có thể in ra bất kỳ đáp án hợp lệ nào.

Ràng buộc

• $2\le N\le {10}^5$, $1\le M\le {10}^5$.
• $1\le U_i<V_i\le N$; giữa hai phòng có tối đa một hành lang; đồ thị liên thông.
• Ít nhất một phòng có đèn đang tắt.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $N\le 100$.
• Subtask 2 ($15\%$ số test): chỉ có một phòng duy nhất có đèn tắt.
• Subtask 3 ($15\%$ số test): các hành lang nối tiếp các phòng thành một dãy theo thứ tự $1,2,3,\dots ,N-1,N$.
• Subtask 4 ($20\%$ số test): tất cả các phòng (trừ phòng $1$) chỉ nối với phòng $1$.
• Subtask 5 ($20\%$ số test): không có ràng buộc gì thêm.

Ví dụ