So, got any packs?

Time limit1sMemory limit512 MB

Summary

Given a DAG of conversation topics, find the fewest edges Junpyo must block so he picks the final topic N first, or report -1 if impossible.

Level: Medium7 of 10
Topics: Game theory, Graph, Dynamic programming, Topological sort
Solved: No attempts yet

Problem

Some players of 돌게임 use the 그팩주 style of speech. It means ending a conversation by saying "So, got any packs?" even when the topic has nothing to do with card packs. Of course, it can only be used in certain flows of conversation, not in any context. Since it forcibly ends the conversation, the other person may feel upset.

Junpyo and Manyoung always have conversations that follow a fixed pattern ending with 그팩주. The pattern consists of $N$ topics and is represented as a directed graph that shows which topic can follow which. For example, an edge from vertex $u$ to vertex $v$ means that topic $v$ can be chosen right after topic $u$ . No cycle exists in which a topic chosen once can be chosen again later.

The two take turns choosing topics. If Junpyo starts the conversation, he chooses the odd-numbered topics, including the first one, and Manyoung chooses the even-numbered ones. Topic $N$ is the 그팩주 topic, so whoever chooses topic $N$ ends the conversation with "So, got any packs?" Every conversation flow converges to topic $N$ .

Junpyo's goal is to be the one who chooses the 그팩주 topic first. To do this, each time Manyoung chooses a topic, Junpyo can glare and prevent him from choosing that topic on this turn. In other words, one glare limits one edge, and he can repeat this on the same turn. Manyoung enjoys seeing Junpyo suffer, so he will choose topics in a way that makes Junpyo glare as much as possible. Of course, if Manyoung takes the 그팩주 topic for himself along the way, that is even better.

A start topic is a topic with no incoming edges. Junpyo picks one of these to begin the conversation. Find the minimum number of glares Junpyo needs to end the conversation with "So, got any packs?".

Input

The first line contains the number of topics $N$ and the number of edges $E$ that form the pattern.

From the second line onward, each of the next $E$ lines contains two integers $u$ and $v$ ( $1 \le u, v \le N$ ), describing an edge in the pattern from $u$ to $v$ . No edge appears more than once.

Output

Print the minimum number of glares Junpyo needs to say "So, got any packs?" first.

If Junpyo cannot end the conversation with "So, got any packs?" no matter what he does, print -1.

Hint

Examples 3 and 4 do not appear in subtask 1.

Examples4

Example 1
Input
```
4 3
1 4
3 1
2 4
```
Expected output
```
0
```
Example 2
Input
```
6 8
1 2
1 3
1 4
2 5
5 6
3 6
4 6
1 6
```
Expected output
```
2
```

Example 3

Input

Expected output

Example 4

Input

Expected output