Hamiltonian Path in a Directed Graph

You are given a directed graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges. Your task is to determine whether there exists a Hamiltonian path in \(G\). A Hamiltonian path is a path that visits every vertex exactly once. More formally, you need to check if there exists an ordering of vertices \(v_1, v_2, \ldots, v_n\) such that for every \(1 \le i < n\), the directed edge \((v_i, v_{i+1})\) is present in \(E\).

Note: Since checking for a Hamiltonian path is NP-complete in general, the input size for this problem is assumed to be small so that a brute-force solution based on examining all vertex permutations is feasible.

inputFormat

The input is given via standard input and consists of multiple lines:

• The first line contains two space-separated integers \(n\) and \(m\) where \(n\) is the number of vertices and \(m\) is the number of directed edges.
• The following \(m\) lines each contain two space-separated integers \(u\) and \(v\), representing a directed edge from vertex \(u\) to vertex \(v\). It is guaranteed that vertices are numbered from 1 to \(n\).

outputFormat

Output a single line to standard output: "YES" if there exists a Hamiltonian path in the graph, or "NO" if there is none.

## sample

4 4
1 2
2 3
3 4
4 1

YES

</p>