CF949C.Data Center Maintenance

BigData Inc. is a corporation that has n data centers indexed from 1 to n that are located all over the world. These data centers provide storage for client data (you can figure out that client data is really big!).

Main feature of services offered by BigData Inc. is the access availability guarantee even under the circumstances of any data center having an outage. Such a guarantee is ensured by using the two-way replication. Two-way replication is such an approach for data storage that any piece of data is represented by two identical copies that are stored in two different data centers.

For each of m company clients, let us denote indices of two different data centers storing this client data as c__i, 1 and c__i, 2.

In order to keep data centers operational and safe, the software running on data center computers is being updated regularly. Release cycle of BigData Inc. is one day meaning that the new version of software is being deployed to the data center computers each day.

Data center software update is a non-trivial long process, that is why there is a special hour-long time frame that is dedicated for data center maintenance. During the maintenance period, data center computers are installing software updates, and thus they may be unavailable. Consider the day to be exactly h hours long. For each data center there is an integer u__j (0 ≤ u__j ≤ h - 1) defining the index of an hour of day, such that during this hour data center j is unavailable due to maintenance.

Summing up everything above, the condition u__c__i, 1 ≠ u__c__i, 2 should hold for each client, or otherwise his data may be unaccessible while data centers that store it are under maintenance.

Due to occasional timezone change in different cities all over the world, the maintenance time in some of the data centers may change by one hour sometimes. Company should be prepared for such situation, that is why they decided to conduct an experiment, choosing some non-empty subset of data centers, and shifting the maintenance time for them by an hour later (i.e. if u__j = h - 1, then the new maintenance hour would become 0, otherwise it would become u__j + 1). Nonetheless, such an experiment should not break the accessibility guarantees, meaning that data of any client should be still available during any hour of a day after the data center maintenance times are changed.

Such an experiment would provide useful insights, but changing update time is quite an expensive procedure, that is why the company asked you to find out the minimum number of data centers that have to be included in an experiment in order to keep the data accessibility guarantees.

BigData 公司是一家拥有 $ n $ 个数据中心的跨国企业，这些数据中心编号从 $ 1 $ 到 $ n $，遍布全球各地。这些数据中心为客户数据提供存储服务（顾名思义，客户数据规模极其庞大！）

BigData 公司所提供服务的一项核心特性，是在任意一个数据中心发生故障的情况下，仍能保障客户数据的访问可用性。该保障通过双向复制（two-way replication）机制实现。所谓双向复制，是指每一份客户数据均以两个完全相同的副本形式，分别存储于两个不同的数据中心中。

对于公司的 $ m $ 个客户中的每一个 $ i $，记其数据所存放的两个不同数据中心的编号为 $ c_{i,1} $ 和 $ c_{i,2} $。

为确保数据中心持续稳定、安全运行，部署在各数据中心服务器上的软件会定期更新。BigData 公司采用每日发布周期，即每天都会向各数据中心服务器部署新版本软件。

数据中心的软件更新是一个复杂且耗时的过程，因此每天专门划出一小时作为数据中心维护窗口。在此维护时段内，服务器正安装软件更新，因而可能处于不可用状态。设一天恰好有 $ h $ 小时长；对每个数据中心 $ j $，给定一个整数 $ u_j $（满足 $ 0 \le u_j \le h-1 $），表示该数据中心在每天的第 $ u_j $ 小时因维护而不可用。

综上所述，为保证客户数据始终可访问，必须对每个客户 $ i $ 满足条件：

$$u_{c_{i,1}} \ne u_{c_{i,2}}$$

否则，当这两个数据中心同时处于各自的维护时段时，该客户的数据将无法访问。

由于世界各地城市偶发的时区调整，部分数据中心的维护时间可能临时变动一小时。公司需对此类情况具备应对能力，因此决定开展一项实验：选定一个非空的数据中心子集，并将其中每个数据中心的维护时间推迟一小时（即：若原维护时间为 $ u_j = h-1 $，则新维护时间变为 $ 0 $；否则变为 $ u_j + 1 $）。然而，该实验不得破坏数据的访问可用性保证——即在所有被选中数据中心的维护时间调整后，在一天中的任意时刻，任何客户的两份数据副本都不得同时处于维护不可用状态。

此项实验将带来宝贵洞察，但调整维护时间是一项高成本操作。因此，公司请你求出：为维持上述数据访问可用性保证，所需参与实验的最少数据中心数量是多少？

The first line of input contains three integers n, m and h (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 2 ≤ h ≤ 100 000), the number of company data centers, number of clients and the day length of day measured in hours.

The second line of input contains n integers _u_1, _u_2, ..., u__n (0 ≤ u__j < h), j-th of these numbers is an index of a maintenance hour for data center j.

Each of the next m lines contains two integers c__i, 1 and c__i, 2 (1 ≤ c__i, 1, c__i, 2 ≤ n, c__i, 1 ≠ c__i, 2), defining the data center indices containing the data of client i.

It is guaranteed that the given maintenance schedule allows each client to access at least one copy of his data at any moment of day.

输入的第一行包含三个整数 $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,\,...,\,u_n$（$0 \leq u_j < h$），其中第 $j$ 个数表示第 $j$ 个数据中心的维护小时索引。

接下来的 $m$ 行中，每行包含两个整数 $c_{i,1}$ 和 $c_{i,2}$（$1 \leq c_{i,1},\,c_{i,2} \leq n$，且 $c_{i,1} \neq c_{i,2}$），表示存储客户端 $i$ 数据的两个数据中心的索引。

保证所给的维护调度方案使得每个客户端在一天中的任意时刻均能访问到其数据的至少一个副本。

In the first line print the minimum possible number of data centers k (1 ≤ k ≤ n) that have to be included in an experiment in order to keep the data available for any client.

In the second line print k distinct integers _x_1, _x_2, ..., x__k (1 ≤ x__i ≤ n), the indices of data centers whose maintenance time will be shifted by one hour later. Data center indices may be printed in any order.

If there are several possible answers, it is allowed to print any of them. It is guaranteed that at there is at least one valid choice of data centers.

第一行输出实验中必须包含的最少数据中心数量 $k$（$1 \le k \le n$），以确保任意客户端均可访问数据。

第二行输出 $k$ 个互不相同的整数 $x_1,\,x_2,\,\dots,\,x_k$（$1 \le x_i \le n$），表示将这些数据中心的维护时间推迟一小时。数据中心索引的输出顺序任意。

若存在多种可行答案，输出任意一种即可。题目保证至少存在一种合法的数据中心选择方案。

Consider the first sample test. The given answer is the only way to conduct an experiment involving the only data center. In such a scenario the third data center has a maintenance during the hour 1, and no two data centers storing the information of the same client have maintenance at the same hour.

On the other hand, for example, if we shift the maintenance time on hour later for the first data center, then the data of clients 1 and 3 will be unavailable during the hour 0.

考虑第一个样例测试。所给答案是针对唯一数据中心进行实验的唯一方式。在此情形下，第三个数据中心在第 1 小时进行维护，且存储同一客户信息的任意两个数据中心不会在同一小时进行维护。

另一方面，例如，若将第一个数据中心的维护时间向后推迟一小时，则客户 1 和客户 3 的数据将在第 0 小时不可用。