Problem E
Escape Routes

Illustration of the two sample inputs. The coloured paths show where each friend goes in order to inspect every street at least once.

As the zombies start approaching your position, you and your surviving friends are devising a plan to evacuate to the next safe area. You know all the streets to the safe area, but don’t yet know of any possible dangers along the way. Some of your friends volunteer to follow different streets to the safe area and report what they find. Time is short, so your friends will only move towards the safe area and never backtrack. How many friends do you need to send out at the same time such that they inspect all the streets to the safe area?

We can model the possible routes as a directed acyclic graph, where the set of vertices $V$ represents junctions where streets can meet or merge and the set of directed edges $E$ represents streets towards the safe area. We number the junctions such that every street strictly increases the junction number. Your friends each start at junction $0$ and end at the safe area $|V|-1$.

Can you find the minimum number of friends you need to send towards the safe area so that every street gets inspected by at least one friend along the way?

Input

Input begins with two space-separated integers $2 \leq |V| \leq 100$ and $|V|-1 \leq |E| \leq {|V| \choose 2}$. The next $|E|$ lines consist of two space-separated integers $0 \leq a < b < |V|$ indicating that a street exists from junction $a$ to $b$. The streets come in lexicographic order, i.e. sorted by closer junction then further junction, and no two streets connect the same two junctions. Every junction and every street lies on some path from $0$ to $|V| - 1$.

Output

Output the smallest number of friends you need to send towards the safe area in order to inspect all the streets.

7 8
0 1
0 2
1 3
2 3
3 4
3 5
4 6
5 6

2

6 7
0 1
0 2
1 3
2 3
2 4
3 5
4 5

3