BigData Inc. 是一家公司,拥有 n 个索引为 1 到 n 的数据中心,这些数据中心位于世界各地。这些数据中心为客户数据提供存储(你可以发现客户数据真的很大!)。
BigData Inc.提供的服务的主要特点是即使在任何数据中心发生故障的情况下也能保证访问可用性。通过使用双向复制来确保这种保证。双向复制是一种数据存储方法,任何数据都由存储在两个不同数据中心的两个相同副本表示。
对于 m 个公司客户中的每一个,让我们将存储该客户数据的两个不同数据中心的索引表示为 ci, 1 和 ci, 2。
为了保持数据中心的运行和安全,数据中心计算机上运行的软件会定期更新。 BigData Inc.的发布周期是一天,这意味着每天都会将新版本的软件部署到数据中心计算机上。
数据中心软件更新是一个不平凡的漫长过程,这就是为什么有一个特殊的长达一小时的时间框架专门用于数据中心维护。维护期间,数据中心计算机正在安装软件更新,因此可能无法使用。考虑这一天正好有 h 小时长。对于每个数据中心,都有一个整数 uj (0 ≤ uj ≤ h - 1) 定义一天中某一小时的索引,使得在这一小时内数据中心 j 由于维护而不可用。
总结以上所有内容,每个客户端都应满足 uci, 1 ≠ uci, 2 的条件,否则在存储数据的数据中心进行维护时,其数据可能无法访问。
由于世界各地不同城市偶尔存在时区变化,部分数据中心的维护时间有时可能会出现一小时的变化。公司应该对这种情况做好准备,这就是为什么他们决定进行一个实验,选择一些非空的数据中心子集,并将其维护时间推迟一个小时(即如果uj = h - 1,则新的维护时间将变为0,否则将变为uj + 1)。尽管如此,这样的实验不应破坏可访问性保证,这意味着在数据中心维护时间更改后,任何客户端的数据在一天中的任何时间都应该仍然可用。
这样的实验将提供有用的见解,但更改更新时间是一个相当昂贵的过程,这就是为什么该公司要求您找出实验中必须包含的最小数据中心数量,以保证数据可访问性。
输入
输入的第一行包含三个整数 n、m 和 h(2 ≤ n ≤ 100 000、1 ≤ m ≤ 100 000、2 ≤ h ≤ 100 000)、公司数据中心的数量、客户端的数量以及以小时为单位的一天长度。
输入的第二行包含n个整数u1, u2, ..., un (0 ≤ uj < h),这些数字中的第j个是数据中心j的维护时间的索引。
接下来的 m 行每行包含两个整数 ci, 1 和 ci, 2 (1 ≤ ci, 1, ci, 2 ≤ n, ci, 1 ≠ ci, 2),定义包含客户端 i 的数据的数据中心索引。
保证给定的维护计划允许每个客户端在一天中的任何时刻至少访问其数据的一份副本。
输出
在第一行中打印实验中必须包含的数据中心的最小可能数量 k (1 ≤ k ≤ n),以便使数据可供任何客户端使用。
在第二行中打印 k 个不同的整数 x1, x2, ..., xk (1 ≤ xi ≤ n),即维护时间将推迟一小时的数据中心的索引。数据中心索引可以按任何顺序打印。
如果有多个可能的答案,则允许打印其中任何一个。保证至少有一种有效的数据中心选择。
示例
输入 #1
3 3 5 4 4 0 1 3 3 2 3 1
输出 #1
1 3
输入 #2
4 5 4 2 1 0 3 4 3 3 2 1 2 1 4 1 3
输出 #2
4 1 2 3 4
注意
考虑第一个样本测试。给出的答案是进行涉及唯一数据中心的实验的唯一方法。在这样的场景下,第三个数据中心在1小时内进行维护,并且存储同一客户端信息的两个数据中心不会在同一时间进行维护。
另一方面,例如,如果我们将第一个数据中心的维护时间移至 1 小时后,则客户端 1 和 3 在 0 小时内将不可用。