17909번 - ISP Merger 다국어

A number of regional Internet Service Providers (ISPs), both big and small have recently been forced into a merger by the government, in an effort to improve service for all. Of course this has been decided without consulting you, the chief network infrastructure officer, and a deadline for when the ISPs should be merged have already been set.

You have a set of n servers, each with a limited number of network sockets that can be used for connecting physically to other servers. Some servers are already linked up in the existing network architecture, and if server 0 is linked to server 2, then 2 is also linked to server 0 (as you use full duplex ethernet Cat6 cables). No server is directly connected to itself, and no two servers are directly linked with more than one connection.

You want to connect the servers to form a single network, such that all servers can reach each other through some sequence of connections. To make the set deadline, you have estimated that you only have time to make k edits to the existing network infrastructure. An edit is either to remove an existing connection between two servers, or to add a new connection between two servers.

Can you connect all the servers to the same network using at most k edits, within the limitations on the number of network sockets in each server?

The first line of the input is three space separated integers n (1 ≤ n ≤ 100 000), the number of servers, m (0 ≤ m ≤ 200 000), the number of existing connections and k (0 ≤ k ≤ 50 000), the number of edits you have time to make. Then follows a line with n integers c₀, c₁, . . . , c_i, . . . , c_n−1, with the i’th number giving the number of network sockets for the i’th server (for all i the capacity is bounded by 1 ≤ c_i < n). Then m lines follow, with two integers uj and vj each, giving the id’s of two servers that are connected in the old network architecture. Servers are 0-indexed, i.e. for every j, it holds that 0 ≤ u_j, v_j < n. A server will never be connected to more servers than it has connection sockets.

Output “yes” on a single line if the servers can be connected to one network by making k or less edits, and “no” if it is not possible.