{"raw_statement":[{"iden":"statement","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 data is really big!).\n\nMain 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.\n\nFor 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.\n\nIn 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.\n\nData 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.\n\nSumming 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.\n\nDue 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.\n\nSuch 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."},{"iden":"input","content":"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.\n\nThe 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_.\n\nEach 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_.\n\nIt is guaranteed that the given maintenance schedule allows each client to access at least one copy of his data at any moment of day."},{"iden":"output","content":"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.\n\nIn 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.\n\nIf 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."},{"iden":"examples","content":"Input\n\n3 3 5\n4 4 0\n1 3\n3 2\n3 1\n\nOutput\n\n1\n3 \n\nInput\n\n4 5 4\n2 1 0 3\n4 3\n3 2\n1 2\n1 4\n1 3\n\nOutput\n\n4\n1 2 3 4"},{"iden":"note","content":"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.\n\nOn 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."}],"translated_statement":[{"iden":"statement","content":"BigData Inc. 是一家拥有 #cf_span[n] 个数据中心的公司，这些数据中心从 #cf_span[1] 到 #cf_span[n] 编号，分布在全球各地。这些数据中心为客户数据提供存储（你可以想象客户数据量非常庞大）。\n\nBigData Inc. 提供服务的主要特性是在任何数据中心发生故障时仍能保证访问可用性。这种保证通过“双向复制”实现。双向复制是一种数据存储方法，其中每一份数据都由两个完全相同的副本表示，分别存储在两个不同的数据中心中。\n\n对于每个公司客户 #cf_span[i]，设存储其数据的两个不同数据中心的索引为 #cf_span[ci, 1] 和 #cf_span[ci, 2]。\n\n为了保持数据中心的运行和安全，数据中心计算机上运行的软件会定期更新。BigData Inc. 的发布周期为一天，意味着每天都会将新版本的软件部署到数据中心计算机上。\n\n数据中心软件更新是一个非平凡的长时间过程，因此专门设置了一个小时的时间段用于数据中心维护。在维护期间，数据中心计算机正在安装软件更新，因此可能不可用。假设一天恰好为 #cf_span[h] 小时。对于每个数据中心，存在一个整数 #cf_span[uj]（#cf_span[0 ≤ uj ≤ h - 1]），表示该数据中心在一天中的第 #cf_span[uj] 小时因维护而不可用。\n\n综上所述，对于每个客户，必须满足条件 #cf_span[uci, 1 ≠ uci, 2]，否则在其数据所在的数据中心进行维护时，该客户的数据可能无法访问。\n\n由于全球各地时区的偶尔变化，某些数据中心的维护时间有时会改变一小时。公司需要为此类情况做好准备，因此决定进行一次实验：选择一个非空的数据中心子集，并将它们的维护时间向后推迟一小时（即，若 #cf_span[uj = h - 1]，则新的维护小时变为 #cf_span[0]，否则变为 #cf_span[uj + 1]）。然而，该实验不应破坏访问保障，即在数据中心维护时间更改后，任何客户的数据在一天中的任何时刻仍应可访问。\n\n此类实验将提供有价值的洞察，但更改更新时间是一项昂贵的操作，因此公司要求你找出为保持数据访问保障所需包含在实验中的最少数据中心数量。\n\n输入的第一行包含三个整数 #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]），分别表示公司数据中心数量、客户数量和一天的小时数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[u1, u2, ..., un]（#cf_span[0 ≤ uj < h]），其中第 #cf_span[j] 个数表示数据中心 #cf_span[j] 的维护小时。\n\n接下来的 #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[ci, 1] 和 #cf_span[ci, 2] 中。\n\n保证给定的维护计划使得每个客户在一天中的任何时刻都能访问至少一份其数据副本。\n\n第一行输出一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ n]），表示为保持数据对所有客户可用所需包含在实验中的最少数据中心数量。\n\n第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]），表示其维护时间将向后推迟一小时的数据中心索引。数据中心索引可以按任意顺序输出。\n\n如果存在多个可能的答案，允许输出其中任意一个。保证至少存在一个有效选择。\n\n考虑第一个样例。所给答案是唯一一种仅涉及一个数据中心的实验方式。在这种情况下，第三个数据中心的维护时间为第 1 小时，且没有两个存储同一客户数据的数据中心在同一小时进行维护。\n\n另一方面，例如，如果我们把第一个数据中心的维护时间向后推迟一小时，则客户 1 和 3 的数据在第 0 小时将不可访问。"},{"iden":"input","content":"输入的第一行包含三个整数 #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[ci, 1] 和 #cf_span[ci, 2] 中。保证给定的维护计划使得每个客户在一天中的任何时刻都能访问至少一份其数据副本。"},{"iden":"output","content":"第一行输出一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ n]），表示为保持数据对所有客户可用所需包含在实验中的最少数据中心数量。第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]），表示其维护时间将向后推迟一小时的数据中心索引。数据中心索引可以按任意顺序输出。如果存在多个可能的答案，允许输出其中任意一个。保证至少存在一个有效选择。"},{"iden":"examples","content":"输入\n3 3 5\n4 4 0\n1 3\n3 2\n3 1\n输出\n1\n3\n\n输入\n4 5 4\n2 1 0 3\n4 3\n3 2\n1 2\n1 4\n1 3\n输出\n4\n1 2 3 4 "},{"iden":"note","content":"考虑第一个样例。所给答案是唯一一种仅涉及一个数据中心的实验方式。在这种情况下，第三个数据中心的维护时间为第 1 小时，且没有两个存储同一客户数据的数据中心在同一小时进行维护。另一方面，例如，如果我们把第一个数据中心的维护时间向后推迟一小时，则客户 1 和 3 的数据在第 0 小时将不可访问。"}],"sample_group":[],"show_order":[],"formal_statement":"**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, \\dots, h-1\\} $, be the maintenance hour of data center $ j $.  \nLet $ C = \\{(c_{i,1}, c_{i,2}) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the set of client-to-data-center mappings, with $ c_{i,1} \\ne c_{i,2} $.  \n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be a non-empty subset of data centers whose maintenance hours are shifted:  \n$$\nu_j' = \n\\begin{cases}\n(u_j + 1) \\bmod h & \\text{if } j \\in S \\\\\nu_j & \\text{otherwise}\n\\end{cases}\n$$\n\n**Constraints**  \n1. For all $ i \\in \\{1, \\dots, m\\} $, $ u_{c_{i,1}}' \\ne u_{c_{i,2}}' $.  \n2. Initially, for all $ i \\in \\{1, \\dots, m\\} $, $ u_{c_{i,1}} \\ne u_{c_{i,2}} $ (guaranteed).  \n\n**Objective**  \nFind the minimum-size non-empty set $ S \\subseteq \\{1, \\dots, n\\} $ such that the constraint above holds after the shift.","simple_statement":null,"has_page_source":false}