YOU: "Your job was putting up Marcus's banners."

RITISHA: "Yeah. I was hoping to do something different. I had this idea for a photo wall — pictures from the last few years of ACPC, plus a polaroid camera so people could add new ones through the night."

YOU: "What happened?"

RITISHA: "Kevin said he already had a photo booth planned and just needed someone on banners. So that became my job. Then a few hours later I watch Zach setting up basically my exact idea."

YOU: "Did you speak to Kevin about it?"

RITISHA: "I wish. I was up a ladder most of the afternoon."

YOU: "And after that?"

RITISHA: "Josh grabbed me for his little interview. Stood there talking to a camera for ten minutes, feeling silly."

After hanging up Marcus' banners, Ritisha wants to check them thoroughly.

The venue consists of ~n~ rooms, numbered from ~1~ to ~n~ and connected by ~m~ directed corridors. Ritisha starts at room ~1~ and walks along the corridors until she reaches a dead end: a room with no outgoing corridors. It is guaranteed that a dead end is reachable (directly or indirectly) from every room.

Some rooms contain one of Marcus' banners. Ritisha checks a banner every time she enters a room with one, even if she has checked it before. Starting at room ~1~ also counts as one visit.

The corridor structure is constrained as follows:

• Every room has at most one incoming corridor, except for rooms lying on a cycle.

• The rooms of each cycle collectively have exactly one incoming corridor from outside the cycle.

• All cycles are pairwise disjoint.

• Every room is reachable from room ~1~.

Equivalently, contracting each cycle into a single node yields a tree rooted at room ~1~.

Is it possible for Ritisha to walk from room ~1~ to some dead end, while checking banners exactly ~k~ times?

Input

The first line contains three integers ~n~, ~m~, and ~k~ (~1 \leq n, m \leq 100~, ~1 \leq k \leq 10^{18}~): the number of rooms, the number of corridors, and the exact number of banner checks Ritisha wants.

The second line contains ~n~ integers ~b_1, \ldots, b_n~, each ~0~ or ~1~, where ~b_i = 1~ if room ~i~ has a banner and ~0~ otherwise.

Each of the next ~m~ lines contains two integers ~u~ and ~v~ (~1 \leq u, v \leq n~), denoting a directed corridor from room ~u~ to room ~v~.

Output

If it is possible for Ritisha to walk through the venue and reach a dead end while checking banners exactly ~k~ times, output Yes. Otherwise, output No.

Example

Input 1

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

Output 1

Yes

Ritisha can check on the banners exactly ~6~ times by following the walk ~1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1 \to 4 \to 6~.

• Ritisha starts at room ~1~, checking the banner there.

  • ~1~ check so far.

• She walks the cycle ~1 \to 2 \to 3~ twice, re-entering room ~1~ each time. Each pass through the cycle checks the banners in rooms ~2~ and ~1~, for ~2~ checks per loop.

  • ~4~ more checks, bringing the total to ~5~.

• After the second loop, she leaves the cycle, continuing on to room ~4~ (no banner) and then room ~6~, checking the banner there.

  • ~1~ more check, for a total of ~6~.

• Room ~6~ has no outgoing corridors, so Ritisha's walk ends there, having checked on banners exactly ~6~ times.

Input 2

9 12 5
0 0 1 1 1 0 0 0 1
1 1
1 2
2 3
3 1
1 4
4 5
5 6
6 7
6 3
2 8
8 2
8 9

Output 2

No

Ritisha can check on the banners exactly ~1~, ~3~, or ~6~ times, among infinitely many other achievable values, but ~5~ is not one of them. She can never reach a dead end after checking the banners exactly ~5~ times.

Input 3

2 2 9999
1 0
1 1
1 2

Output 3

Yes