Bảo trì trung tâm dữ liệu

Một công ty vận hành $n$ trung tâm dữ liệu, đánh số từ $1$ đến $n$. Mỗi ngày có đúng $h$ giờ (đánh số từ $0$ đến $h-1$). Trung tâm thứ $j$ có một giờ bảo trì $u_j$ trong ngày — trong giờ đó nó tạm thời không phục vụ.

Công ty có $m$ khách hàng. Dữ liệu của khách hàng thứ $i$ được lưu đồng thời ở hai trung tâm khác nhau $c_{i,1}$ và $c_{i,2}$, để đảm bảo dữ liệu luôn truy cập được. Để giữ điều đó, hai trung tâm lưu cùng một khách hàng phải có giờ bảo trì khác nhau, tức là $u_{c_{i,1}}\ne u_{c_{i,2}}$.

Lịch hiện tại đã thoả mãn điều kiện trên. Bây giờ công ty muốn chọn một tập con khác rỗng các trung tâm và dời giờ bảo trì của mọi trung tâm trong tập đó lên muộn hơn $1$ giờ (nếu $u_j=h-1$ thì giờ mới là $0$, ngược lại là $u_j+1$). Sau khi dời, điều kiện $u_{c_{i,1}}\ne u_{c_{i,2}}$ vẫn phải đúng cho mọi khách hàng.

Hãy tìm tập con như vậy với kích thước nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $h$.
• Dòng thứ hai chứa $n$ số nguyên $u_1,u_2,\dots ,u_n$ ($0\le u_j<h$).
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $c_{i,1}$ và $c_{i,2}$ ($c_{i,1}\ne c_{i,2}$).

Dữ liệu vào đảm bảo lịch ban đầu đã hợp lệ và luôn tồn tại ít nhất một tập con đáp án.

Dữ liệu ra

• Dòng đầu: số nguyên $k$ — kích thước nhỏ nhất của tập con cần dời.
• Dòng thứ hai: $k$ số nguyên phân biệt — chỉ số các trung tâm trong tập con. Nếu có nhiều đáp án tối ưu, in ra bất kỳ đáp án nào.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le {10}^5$
• $2\le h\le {10}^5$
• $1\le c_{i,1},c_{i,2}\le n$

Ví dụ