Mutually Reachable Cities

In this problem, you are given a directed graph representing a network of cities. The graph has (n) cities and (m) directed roads. Additionally, you are allowed to add at most (k) new roads. Your task is to determine whether it is possible to make the city network strongly connected by adding at most (k) roads. A network is strongly connected if for every pair of distinct cities (u) and (v), there is a path from (u) to (v) and a path from (v) to (u).

Note: The input roads are directed, and the added roads can be chosen arbitrarily between cities.

inputFormat

The input is given from standard input and has the following format:

The first line contains three integers (n), (m), and (k), where (n) is the number of cities, (m) is the number of existing roads, and (k) is the maximum number of roads you can add. Each of the following (m) lines contains two integers (u) and (v), representing a directed road from city (u) to city (v).

outputFormat

Output a single line to standard output: "YES" if it is possible to add at most (k) roads so that every city is reachable from every other city (i.e. the graph becomes strongly connected), or "NO" otherwise.## sample

4 4 2
1 2
2 3
3 4
4 1

YES