ISP Merger

Time limit2sMemory limit512 MB

Summary

Decide whether at most k edge additions or removals can make a graph connected while keeping each vertex's degree within its socket limit.

Level: Medium6 of 10
Topics: Graph, Greedy, Union-find
Solved: No attempts yet

Problem

Several regional Internet Service Providers (ISPs), both large and small, have been forced into a merger by the government to improve service for everyone. The government made this decision without consulting you, the chief network infrastructure officer, and a deadline has already been set.

You manage a set of $n$ servers. Each server has a limited number of network sockets for physically connecting to other servers. Some servers are already linked in the existing network. If server 0 is linked to server 2, then server 2 is also linked to server 0, because the links are full duplex Ethernet Cat6 cables. No server is linked to itself, and no two servers are linked by more than one connection.

You want to connect the servers into a single network, so that every server can reach every other server through some sequence of connections. You have time to make only $k$ edits to the existing infrastructure. An edit either removes an existing connection between two servers or adds a new connection between two servers.

Can you connect all the servers into one network using at most $k$ edits, while staying within each server's socket limit?

Input

The first line contains three space separated integers $n$ , $m$ , and $k$ , where $n$ is the number of servers, $m$ is the number of existing connections, and $k$ is the number of edits you can make. $1 \le n \le 100000$ , $0 \le m \le 200000$ , and $0 \le k \le 50000$ .

The next line contains $n$ integers $c_0, c_1, ..., c_{n-1}$ , where $c_i$ is the number of network sockets on server $i$ . Each capacity satisfies $1 \le c_i < n$ .

Each of the next $m$ lines contains two integers $u_j$ and $v_j$ , the IDs of two servers that are connected in the existing network. Servers are numbered from 0. Every server is connected to no more servers than it has sockets.

Output

Print "yes" on a single line if all servers can be connected into one network using at most $k$ edits. Otherwise, print "no".

Examples3

Example 1
Input
```
4 5 2
3 3 3 3
0 1
0 3
1 3
1 2
2 3
```
Expected output
```
yes
```
Example 2
Input
```
5 4 4
1 1 2 2 2
0 1
2 3
3 4
4 2
```
Expected output
```
yes
```
Example 3
Input
```
3 0 3
1 1 1
```
Expected output
```
no
```