The company Maija is working at has created itself a hellish microservice architecture. Blissfully unaware of the situation, the middle management wishes to introduce recursive microservices - microservices that have the capability call themselves but with different parameters! However, they have realized the inherent danger in this design and have tasked Maija to prevent any sort of cyclical service calling loops from forming.

The sighs of the system architect have gradually been getting longer and more turbulent. Maija figures the guy is going to burn out any moment now, so she decides to walk the extra mile to help him and restricts the new feature even more.

The recursive micro-service takes a single positive integer as input, which is less than or equal to n. There are m relations in the system: input a_i calls input b_i. Maija decides that no service should cause more than X service calls. Help Maija determine whether the recursive microservice satisfies this constraint.

Input

The first line contains three integers n,m, and X. The i-th of next m following line contains two integers a_i and b_i.

Output

Print "Yes" if the microservice satisfies the condition and "No" otherwise.

Constraints

• 2 \leq n \leq 10^5
• 1 \leq m \leq 2 \times 10^5
• 1 \leq X \leq 10^{12}
• 1 \leq a_i, b_i \leq n
• a_i \neq b_i
• (a_i, b_i) \neq (a_j, b_j) if i \neq j

Example 1

Input:

5 6 8
5 3
3 4
3 2
3 1
4 1
2 1

Output:

Yes

Example 2

Input:

5 7 1000000000000
2 4
3 2
3 5
3 1
5 3
5 4
1 2

Output:

No

Example 3

Input:

4 6 7
1 2
1 3
1 4
2 3
2 4
3 4

Output:

No