English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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.
BigData Inc. 是一家拥有 #cf_span[n] 个数据中心的公司，这些数据中心从 #cf_span[1] 到 #cf_span[n] 编号，分布在全球各地。这些数据中心为客户数据提供存储（你可以想象客户数据量非常庞大！）。
BigData Inc. 提供服务的主要特性是在任意数据中心发生故障时仍能保证访问可用性。这种保证通过“双向复制”实现。双向复制是一种数据存储方法，其中每一份数据都由两个完全相同的副本表示，分别存储在两个不同的数据中心中。
对于每个公司客户 #cf_span[i]，我们用 #cf_span[ci, 1] 和 #cf_span[ci, 2] 表示存储该客户数据的两个不同数据中心的索引。
为了保持数据中心的运行和安全，运行在数据中心计算机上的软件会定期更新。BigData Inc. 的发布周期为一天，意味着每天都会将新版本的软件部署到数据中心计算机上。
数据中心软件更新是一个非平凡的长时间过程，因此专门安排了一个小时的时间段用于数据中心维护。在维护期间，数据中心计算机正在安装软件更新，因此可能不可用。假设一天恰好为 #cf_span[h] 小时。对于每个数据中心，有一个整数 #cf_span[uj]（#cf_span[0 ≤ uj ≤ h - 1]）表示一天中的某个小时索引，在此小时内，数据中心 #cf_span[j] 由于维护而不可用。
综上所述，对于每个客户，必须满足条件 #cf_span[uci, 1 ≠ uci, 2]，否则在其数据存储的数据中心进行维护时，该客户的数据可能无法访问。
由于全球各地时区的偶尔变化，某些数据中心的维护时间有时会改变一小时。公司需要为此类情况做好准备，因此决定进行一次实验：选择某个非空的数据中心子集，将其维护时间向后推迟一小时（即，若 #cf_span[uj = h - 1]，则新的维护小时变为 #cf_span[0]，否则变为 #cf_span[uj + 1]）。然而，该实验不应破坏访问保证，即在数据中心维护时间更改后，任何客户的数据在一天中的任何时刻都应仍可访问。
此类实验将提供有价值的洞察，但更改更新时间是一项昂贵的操作，因此公司要求你找出为保持数据访问保证所需包含在实验中的最少数据中心数量。
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[h]（#cf_span[2 ≤ n ≤ 100 000], #cf_span[1 ≤ m ≤ 100 000], #cf_span[2 ≤ h ≤ 100 000]），分别表示公司数据中心的数量、客户数量和以小时为单位的一天长度。
第二行输入包含 #cf_span[n] 个整数 #cf_span[u1, u2, ..., un]（#cf_span[0 ≤ uj < h]），其中第 #cf_span[j] 个数表示数据中心 #cf_span[j] 的维护小时索引。
接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[ci, 1] 和 #cf_span[ci, 2]（#cf_span[1 ≤ ci, 1, ci, 2 ≤ n], #cf_span[ci, 1 ≠ ci, 2]），表示存储客户 #cf_span[i] 数据的数据中心索引。
保证给定的维护计划允许每个客户在一天中的任何时刻都能访问至少一份其数据副本。
第一行输出一个最小可能的数据中心数量 #cf_span[k]（#cf_span[1 ≤ k ≤ n]），这些数据中心必须包含在实验中，以确保任何客户的数据都可用。
第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]），表示其维护时间将向后推迟一小时的数据中心索引。数据中心索引可以按任意顺序输出。
如果有多个可能的答案，允许输出其中任意一个。保证至少存在一种有效选择。
考虑第一个样例。给出的答案是仅涉及一个数据中心的唯一实验方式。在此情况下，第三个数据中心在第 1 小时进行维护，且没有两个存储同一客户数据的数据中心在同一小时进行维护。
另一方面，例如，如果我们把第一个数据中心的维护时间向后推迟一小时，则客户 1 和 3 的数据将在第 0 小时不可用。
## Input
输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[h]（#cf_span[2 ≤ n ≤ 100 000], #cf_span[1 ≤ m ≤ 100 000], #cf_span[2 ≤ h ≤ 100 000]），分别表示公司数据中心的数量、客户数量和以小时为单位的一天长度。第二行输入包含 #cf_span[n] 个整数 #cf_span[u1, u2, ..., un]（#cf_span[0 ≤ uj < h]），其中第 #cf_span[j] 个数表示数据中心 #cf_span[j] 的维护小时索引。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[ci, 1] 和 #cf_span[ci, 2]（#cf_span[1 ≤ ci, 1, ci, 2 ≤ n], #cf_span[ci, 1 ≠ ci, 2]），表示存储客户 #cf_span[i] 数据的数据中心索引。保证给定的维护计划允许每个客户在一天中的任何时刻都能访问至少一份其数据副本。
## Output
第一行输出一个最小可能的数据中心数量 #cf_span[k]（#cf_span[1 ≤ k ≤ n]），这些数据中心必须包含在实验中，以确保任何客户的数据都可用。第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]），表示其维护时间将向后推迟一小时的数据中心索引。数据中心索引可以按任意顺序输出。如果有多个可能的答案，允许输出其中任意一个。保证至少存在一种有效选择。
[samples]
## Note
考虑第一个样例。给出的答案是仅涉及一个数据中心的唯一实验方式。在此情况下，第三个数据中心在第 1 小时进行维护，且没有两个存储同一客户数据的数据中心在同一小时进行维护。另一方面，例如，如果我们把第一个数据中心的维护时间向后推迟一小时，则客户 1 和 3 的数据将在第 0 小时不可用。
**Definitions**
Let $ n, m, h \in \mathbb{Z}^+ $ denote the number of data centers, clients, and hours per day, respectively.
Let $ \mathbf{u} = (u_1, u_2, \dots, u_n) $, where $ u_j \in \{0, 1, \dots, h-1\} $, be the maintenance hour of data center $ j $.
Let $ C = \{(c_{i,1}, c_{i,2}) \mid i \in \{1, \dots, m\}\} $ be the set of client data center pairs, with $ c_{i,1} \ne c_{i,2} $.
Let $ S \subseteq \{1, 2, \dots, n\} $ be a non-empty subset of data centers whose maintenance hours are shifted:
$$
u_j' =
\begin{cases}
(u_j + 1) \bmod h & \text{if } j \in S \\
u_j & \text{otherwise}
\end{cases}
$$
**Constraints**
1. For all $ i \in \{1, \dots, m\} $, $ u_{c_{i,1}}' \ne u_{c_{i,2}}' $.
2. Initially, $ u_{c_{i,1}} \ne u_{c_{i,2}} $ for all $ i $.
**Objective**
Find the minimum size $ |S| $ and a corresponding set $ S $ such that the constraint holds after the shift.
API Response (JSON)
{
"problem": {
"name": "C. Data Center Maintenance",
"description": {
"content": "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 da",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF949C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 da...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "BigData Inc. 是一家拥有 #cf_span[n] 个数据中心的公司，这些数据中心从 #cf_span[1] 到 #cf_span[n] 编号，分布在全球各地。这些数据中心为客户数据提供存储（你可以想象客户数据量非常庞大！）。\n\nBigData Inc. 提供服务的主要特性是在任意数据中心发生故障时仍能保证访问可用性。这种保证通过“双向复制”实现。双向复制是一种数据存储方法，其中每一份数...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, h \\in \\mathbb{Z}^+ $ denote the number of data centers, clients, and hours per day, respectively. \nLet $ \\mathbf{u} = (u_1, u_2, \\dots, u_n) $, where $ u_j \\in \\{0, 1, \\...",
"is_translate": false,
"language": "Formal"
}
]
}