Minimum Workers for Complete Ski Track Inspection

On a mountainside there is a network of ski tracks connecting flat areas, and a ski lift that takes workers from the mountain top (the highest point) to the mountain bottom (the lowest point). Every ski track is a downhill segment of the journey from the top to the bottom. Each morning a team of workers takes the lift up to the top and then each selects a ski route—a path from the top to the bottom—to inspect the tracks. A worker may only slide once, and several workers may share part or all of their route. In other words, if a track (edge) is inspected by any worker it is considered checked.

The network of ski tracks is represented as a directed acyclic graph (DAG) with n nodes and m edges. Each node represents a flat area with a unique altitude. Every edge goes from a higher-altitude node to a lower-altitude node. It is guaranteed that every edge lies on at least one path from the unique source (mountain top, assumed to be node 1) to the unique sink (mountain bottom, assumed to be node n).

Your task is to determine the minimum number of workers (i.e. the minimum number of s-t paths) required so that by assigning each worker one route from the top to the bottom, every ski track (edge) is inspected by at least one worker.

Formally, let the set of edges be \(E\). We want to select a collection \(\mathcal{P}\) of paths (each starting at node 1 and ending at node n) such that:

[ \bigcup_{P \in \mathcal{P}} P = E, \quad \text{and} \quad |\mathcal{P}| \text{ is minimized.} ]

Note: Any formula (such as the one above) must be written in \(\LaTeX\) format.

inputFormat

The input begins with a line containing two integers n and m (2 ≤ n ≤ 20, 1 ≤ m ≤ 100) representing the number of nodes and the number of ski tracks respectively. The nodes are numbered from 1 to n, where node 1 is the mountain top and node n is the mountain bottom. Each of the following m lines contains two integers u and v indicating there is a ski track from node u to node v (with u < v in terms of altitude).

outputFormat

Output a single integer representing the minimum number of s-t paths required to cover all tracks (edges).

sample

3 2
1 2
2 3

1