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 \cdot 10^5~.

Input

• 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~.

Output

• 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 \cdot 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.

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.

Các số trên cùng một dòng của dữ liệu vào và kết quả được ghi cách nhau bởi dấu cách.

Scoring

Sample Input 1

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

Sample Output 1

6
1 3 2 4 3 2

Notes

• Trạng thái đèn ban đầu: Phòng ~1~: Tắt, Phòng ~2~: Bật, Phòng ~3~: Bật, Phòng ~4~: Tắt.

• Sau ~4~ bước đầu: ~\rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 4~. Trạng thái đèn: Phòng ~1,4~: Bật; Phòng ~2,3~: Tắt.

• Sau ~2~ bước cuối: ~\rightarrow 3 \rightarrow 2~. Tất cả đèn các phòng đều bật.