Counting Distinct Paths in a Directed Acyclic Graph

You are given a directed graph with n nodes labeled from 1 to n and m directed edges. The graph is expected to be a Directed Acyclic Graph (DAG); however, if the input graph contains a cycle then the answer is defined to be 0.

Your task is to count the number of distinct simple paths (i.e. paths that do not visit any node more than once) from node 1 to node n. In case the graph has a cycle (and thus is not a DAG), output 0.

Note: A simple path is a path that does not contain repeated vertices. All formulas should be represented in LaTeX format; for example, the number of nodes is given by $n$ and the number of edges by $m$.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer $n$ $(1 \leq n)$, the number of nodes in the graph.
• The second line contains an integer $m$, the number of directed edges.
• Each of the following $m$ lines contains two space-separated integers $u$ and $v$ $(1 \leq u, v \leq n)$, representing a directed edge from node $u$ to node $v$.

outputFormat

Output via standard output (stdout) a single integer representing the number of distinct simple paths from node 1 to node $n$. If the graph contains a cycle (i.e. it is not a DAG), output 0.## sample

1
0

1