Bạn đã không thể dừng lại ở việc tưởng tượng... Bạn thật sự thực hiện vụ đột nhập, và lúc đầu mọi chuyện diễn ra đúng kế hoạch. Nhưng việc liên lạc với trợ lý lại hỏng bét — cũng dễ đoán mà, phải không? Thay vì trở về Lübeck an toàn, giờ bạn mắc kẹt trên một hòn đảo nhỏ, còn tàu ngầm thì hết nhiên liệu.

Để về kịp lễ trao giải BOI, bạn phải đến được chuyến phà ở phía bên kia đảo. Tuy nhiên, cư dân địa phương có những truyền thống kỳ lạ. Cà vạt rất quan trọng với họ, và mỗi ngôi làng có một màu cà vạt yêu thích, có thể thay đổi theo thời gian.

Một bài viết trên mạng cho biết ban đầu các làng khác nhau thích các màu cà vạt khác nhau. Đáng tiếc là bài viết đã quá cũ. Kể từ đó, mỗi tuần có đúng một ngôi làng thuyết phục một làng láng giềng chuyển sang thích cùng màu cà vạt với mình. Hai làng là láng giềng nếu được nối trực tiếp bởi một con đường. Việc thuyết phục chỉ có thể xảy ra nếu tổng số người trên toàn đảo thích màu cà vạt của làng thứ nhất ít nhất bằng tổng số người thích màu cà vạt của làng thứ hai. Thời gian đã trôi qua đủ lâu để giờ đây tất cả cư dân trên đảo đều thích cùng một màu cà vạt.

Bạn gần như chắc chắn rằng dân đảo sẽ không cho mình đi qua nếu không đeo cà vạt đúng màu họ thích. Vì vậy, để đến được phà, bạn định đeo một chiếc cà vạt cho mỗi màu mà dân đảo có thể đang thích. Nhưng đeo quá nhiều cà vạt lại khiến bạn trông đáng ngờ. Hãy viết chương trình dựa trên mô tả hòn đảo để xác định những màu cà vạt bạn cần đeo.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(M\), lần lượt là số làng và số đường trên đảo. Các làng được đánh số từ \(1\) đến \(N\).

Dòng tiếp theo chứa \(N\) số nguyên \(s_1,\ldots,s_N\), trong đó \(s_i\) là số dân của làng \(i\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a,b\), với \(1\le a,b\le N\) và \(a\ne b\), biểu thị một con đường nối làng \(a\) với làng \(b\). Từ bất kỳ làng nào cũng có thể đi đến mọi làng khác, trực tiếp hoặc qua các làng trung gian.

Dữ liệu ra

In một chuỗi độ dài \(N\) chỉ gồm các ký tự 0 và 1. Ký tự thứ \(i\) bằng 1 khi và chỉ khi có thể xảy ra việc tất cả cư dân trên đảo hiện nay đều thích màu cà vạt mà làng \(i\) yêu thích ban đầu.

Ràng buộc

• \(1\le N\le200\,000\).
• \(0\le M\le200\,000\).
• \(1\le s_i\le10^9\) với \(1\le i\le N\).
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(10\) điểm: \(N\le2\,000\) và \(M\le2\,000\).
2. \(10\) điểm: \(s_1\ge s_2\ge\cdots\ge s_N\), và mỗi làng \(b>1\) được nối trực tiếp với đúng một làng \(a\) có \(a<b\).
3. \(15\) điểm: hai làng \(a,b\) được nối trực tiếp khi và chỉ khi \(|a-b|=1\).
4. \(30\) điểm: có nhiều nhất \(10\) giá trị khác nhau trong các số dân \(s_1,\ldots,s_N\).
5. \(35\) điểm: không có ràng buộc thêm.

Ví dụ

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

1110

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

1110