题目描述

题目译自 Open Olympiad in Informatics 2018 Day1 T2 「Обновление дата-центров / Data Center Maintenance」。

BigData Inc. 公司拥有 $n$ 个数据中心，编号从 $1$ 到 $n$，分布在全球各地。这些数据中心存储着公司客户的数据（正如公司名称所暗示的——大数据！）。

BigData Inc. 公司提供的核心服务是保证即使在某些数据中心不可用时，用户数据仍然可以访问。这种保证通过双重复制数据来实现。双重复制是一种方法，即任何数据都以两个相同的副本存储在两个不同的数据中心中。

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

为了维持数据中心的运行和数据的安全性，每个数据中心的软件需要定期更新。BigData Inc. 公司的发布周期为一天，即每天都会为数据中心的每台计算机发布新版本的软件。

更新一个包含多台计算机的数据中心是一项复杂且耗时的任务，因此为每个数据中心分配了一个一小时的时间窗口，在此期间数据中心的计算机将进行更新，可能会不可用。我们假设一天有 $h$ 个小时。因此，对于每个数据中心，固定了一个整数 $u_j$ $(0 \leq u_j \leq h - 1)$，表示一天中数据中心 $j$ 因计划更新而不可用的小时编号。

根据上述情况，对于任何客户，必须满足条件 $u_{c_{i,1}} \neq u_{c_{i,2}}$，因为如果两个数据中心同时更新，公司将无法确保客户能够访问其数据。

由于世界各地不同国家和城市的时钟调整，某些数据中心的更新时间可能会向前偏移一小时。为了应对突发情况，公司管理层希望进行一次演习，在演习中将选择一个非空的数据中心子集，并将这些数据中心的更新时间在一天内向后偏移一小时（即如果 $u_j = h - 1$，则新的更新小时为 $0$，否则为 $u_j + 1$）。同时，演习不得破坏数据可用性的保证，即在更新时间调整后，仍需确保任何客户的任何数据副本在任何小时内至少有一个是可访问的。

演习是一项有益但耗时且昂贵的活动，因此公司管理层向你求助，希望你能确定一个最小规模的非空数据中心子集，以便仅在该子集上进行演习。

输入格式

第一行包含三个整数 $n, m, h$ $(2 \leq n \leq 100000, 1 \leq m \leq 100000, 2 \leq h \leq 100000)$，分别表示公司数据中心的数量、公司客户的数量和一天中的小时数。

第二行包含 $n$ 个整数 $u_1, u_2, \ldots, 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$ 数据的两个数据中心的编号。

保证在给定的更新时间表下，任何客户在任何时刻至少有一个数据副本是可访问的。

输出格式

第一行输出一个整数 $k$ $(1 \leq k \leq n)$，表示演习必须涉及的最小数据中心数量，以确保不丢失数据可用性保证。第二行输出 $k$ 个不同的整数，即数据中心的编号 $x_1, x_2, \ldots, x_k$ $(1 \leq x_i \leq n)$，这些数据中心在演习中将更新时间向后偏移一小时。数据中心的编号可以按任意顺序输出。

如果存在多种可能的答案，可以输出任意一种。保证至少存在一个满足题目条件的解。

3 3 5
4 4 0
1 3
3 2
3 1

1
3

在第一个样例中，提供的答案是唯一一种仅涉及一个数据中心进行演习的方式。在这种情况下，第三个服务器的更新时间调整为一天的第一个小时，并且存储同一用户数据的任何两个服务器不会在同一小时内更新。

另一方面，例如，仅将第一个服务器的更新时间向前偏移一小时是不可行的——在这种情况下，用户 $1$ 和 $3$ 的数据将在第 $0$ 小时内不可用。

4 5 4
2 1 0 3
4 3
3 2
1 2
1 4
1 3

4
1 2 3 4

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。