데이터 센터 점검

BigData Inc.는 전 세계에 흩어진 $n$개의 데이터 센터를 운영한다. 데이터 센터에는 1부터 $n$까지 번호가 붙어 있으며, 고객 데이터를 저장한다. 이 회사는 어떤 데이터 센터에 장애가 나더라도 고객이 데이터에 접근할 수 있다고 보장한다. 이 보장은 이중 복제(two-way replication)로 이루어진다. 이중 복제에서는 모든 데이터가 서로 다른 두 데이터 센터에 저장된 동일한 사본 두 개로 표현된다.

고객은 $m$명이다. 고객 $i$의 데이터를 저장하는 서로 다른 두 데이터 센터의 번호를 $c_{i,1}$과 $c_{i,2}$라고 하자.

각 데이터 센터의 소프트웨어는 매일 업데이트된다. 하루는 정확히 $h$시간이며, 데이터 센터 $j$에는 그 시간 동안 접근할 수 없는 점검 시각 $u_j$($0 \leq u_j \leq h-1$)가 있다. 모든 고객에 대해 $u_{c_{i,1}} \neq u_{c_{i,2}}$가 성립해야 한다. 그렇지 않으면 두 사본이 동시에 멈추어 해당 고객의 데이터에 접근할 수 없다.

시간대 변경으로 일부 데이터 센터의 점검 시각이 한 시간씩 바뀌는 경우가 있다. 회사는 이에 대비해 실험을 하려 한다. 공집합이 아닌 데이터 센터 부분집합을 골라 그 점검 시각을 한 시간 뒤로 옮긴다. $u_j = h-1$이면 새 점검 시각은 0이 되고, 그 외에는 $u_j+1$이 된다. 실험 후에도 접근성 보장은 유지되어야 한다. 즉 하루의 모든 시각에 모든 고객은 적어도 하나의 사본에 접근할 수 있어야 한다.

점검 시각을 바꾸는 데는 비용이 많이 드므로, 실험에 포함해야 하는 데이터 센터의 최소 개수를 구하라.

첫 줄에 세 정수 $n$, $m$, $h$($2 \leq n \leq 100\,000$, $1 \leq m \leq 100\,000$, $2 \leq h \leq 100\,000$)가 주어진다. 둘째 줄에는 $n$개의 정수 $u_1, u_2, \ldots, u_n$($0 \leq u_j < h$)이 주어진다. 이어지는 $m$개의 줄에는 두 정수 $c_{i,1}$, $c_{i,2}$($1 \leq c_{i,1}, c_{i,2} \leq n$, $c_{i,1} \neq c_{i,2}$)가 주어진다. 주어진 일정에서는 하루의 어느 순간에도 모든 고객이 적어도 하나의 사본에 접근할 수 있음이 보장된다.

첫 줄에 실험에 포함해야 하는 데이터 센터의 최소 개수 $k$($1 \leq k \leq n$)를 출력한다. 둘째 줄에는 점검 시각을 한 시간 뒤로 옮길 데이터 센터의 서로 다른 번호 $x_1, x_2, \ldots, x_k$($1 \leq x_i \leq n$)를 출력한다. 출력 순서는 상관없다. 답이 여러 개이면 그중 아무거나 출력해도 된다. 유효한 선택이 적어도 하나 존재함이 보장된다.

첫 번째 예제에서는 데이터 센터 하나만 고르는 방법 중 이 답이 유일하다. 데이터 센터 3은 시각 1에 점검을 받고, 같은 고객의 데이터를 저장하는 두 데이터 센터는 같은 시각에 점검을 받지 않는다. 반대로 데이터 센터 1의 점검 시각을 옮기면, 고객 1과 3의 데이터는 시각 0에 접근할 수 없게 된다.