Hamiltonian Path in Directed Graph

You are given a directed graph with n nodes and m edges. Your task is to determine whether there exists a Hamiltonian Path from node s to node t.

A Hamiltonian Path is defined as a path that visits every vertex in the graph exactly once. In other words, if the path is represented as an ordered sequence of nodes \(p_1, p_2, \dots, p_n\), then the following conditions must hold:

• \(p_1 = s\) and \(p_n = t\)
• For every consecutive pair \(p_i, p_{i+1}\) (for \(1 \le i < n\)), there must be a directed edge from \(p_i\) to \(p_{i+1}\) in the graph.
• All nodes \(1\) to \(n\) appear exactly once in the path.

If such a path exists, print YES; otherwise, print NO.

inputFormat

The input is given from STDIN in the following format:

n m s t
u1 v1
u2 v2
... 
um vm

where:

• n is the number of nodes.
• m is the number of edges.
• s is the starting node and t is the target node.
• Each of the next m lines contains two integers u and v representing a directed edge from node u to node v.

outputFormat

Output YES if there exists a Hamiltonian Path from node s to node t; otherwise, output NO. The output should be printed to STDOUT.

## sample

4 5 1 4
1 2
2 3
3 4
1 3
4 3

YES