CF949C Data Center Maintenance

比眉伴天荒 2022-05-28 05:48 96阅读 0赞

## 题目 ##

[Data Center Maintenance:CodeForces - 949C ][Data Center Maintenance_CodeForces - 949C]

## 题意: ##

BigData公司是一家拥有n个数据中心的公司，编号1~n。这些数据中心为客户端数据提供存储。  
在任何数据中心发生故障的情况下，BigData公司需保证数据可用。这种保证是通过使用双向复制来保证的。双向复制是数据存储的一种方法，任何数据都由两个存储在两个不同数据中心的相同副本表示。  
有m个公司客户，对于其中的每一个客户，存储此客户数据的两个不同数据中心的序号，分别表示为ci，1  c i ， 1 和ci，2  c i ， 2 。  
数据中心会定期升级。每天每个数据中心都会花费一个小时更新软件。  
当某台服务器在维护时，其将不可访问。一天的时间长达整整h小时。对于每个数据中心，都有一个整数uj(0≤uj≤h−1)  u j ( 0 ≤ u j ≤ h − 1 ) ，表示数据中心j在一天中的第uj  u j 小时内因维护而不可用。  
综上，必须保证所有服务器的uci,1≠uci,2  u c i , 1 ≠ u c i , 2 ，否则就有会用户在某时刻无法访问所需数据。  
由于世界各地不同城市偶尔会发生时区变化，有些数据中心的维护时间有时可能会推迟一个小时。 公司应该为这种情况做好准备，他们决定进行一些试验性实验，选择一些非空子集的数据中心，将他们的维护时间推迟一小时（即如果uj=h−1  u j = h − 1 ，那么新的维护时间将变为0，否则它将变成uj\+1  u j + 1 ）。  
这些实验将提供宝贵的经验，但更改更新时间是相当昂贵的过程，这就是为什么该公司要求您找出可以进行实验的最小非空集合，以便保持数据的可访问性。

## 输入格式： ##

第一行输入包含三个整数n，m和h（2≤n≤100 000，1≤m≤100 000，2≤h≤100 000），表示公司数据中心数量，客户数量和一天包含的小时数。

第二行输入包含n个整数u1，u2，...，un（0≤uj<h）  u 1 ， u 2 ， . . . ， u n （ 0 ≤ u j < h ） ，表示第j个数据中心的维护时间

每个接下来的m行包含两个整数ci,1和ci,2（1≤ci,1，ci,2≤n，ci,1≠ci,2）  c i , 1 和 c i , 2 （ 1 ≤ c i , 1 ， c i , 2 ≤ n ， c i , 1 ≠ c i , 2 ） ，表示包含客户i的数据的两个数据中心序号。  
输入数据保证每个客户在任何时刻能至少访问他的一个数据副本。

## 输出格式: ##

在第一行中，输出必须包含在实验中的最小可能的数据中心的数量k（1≤k≤n）（在保证所有数据可用性的前提下）。  
在第二行输出k个不同的整数x1，x2，…，xk（1≤xi≤n），这些数据中心的维护时间将延后一小时。数据中心序号递增。  
如果有几个可能的答案，可以输出其中的任何一个。

## 样例: ##

inputCopy
    3 3 5
    4 4 0
    1 3
    3 2
    3 1
    output
    1
    3

inputCopy
    4 5 4
    2 1 0 3
    4 3
    3 2
    1 2
    1 4
    1 3
    output
    4
    1 2 3 4

## Note ##

在第一个样例中。给出的答案是唯一可行的实验。在这种情况下，第三个数据中心将在第一个小时内进行维护。  
否则，例如，如果我们将延后1小时维护的服务器换成第一个数据中心，则服务器1和3的数据将在0小时时刻都不可用。

[Data Center Maintenance_CodeForces - 949C]: http://codeforces.com/problemset/problem/949/C