Problem G. Guaranteed win ≡

Statement

A game company produced new high-profile car racing game for set-top boxes. To promote the game, company organized a tournament with a big cash prize.

A game is designed for two players racing each other — each game ends in one of players winning and the other one losing. The tournament is organized as a round-robin between all N players (i. e. each player plays versus each other exactly once). After every game, winner gets one point towards his score. When all games are played, players are sorted by the descending score. If exactly one player gets the top score, he is declared an absolute champion and takes all the prize money. Otherwise, money is divided between all players with the same top score.

Young gamer Vasya participates in the tournament. In the middle of the tournament, when M games were already finished, he decided to find out: can he still become an absolute champion based on current results, and, if so, how many more games he must win to ensure absolute championship regardless of other players' results and, if he can afford to lose some of his unplayed games, regardless of which players he will win or lose against.

Input file format

Input file contains integers N M followed by M pairs W_i L_i, meaning that player number W_i won against player number L_i. Vasya is player number 1.

Output file format

Output file must contain a single integer — number of games to be won. If there is no chance left for Vasya to win whole prize, output −1.

Constraints

2 ≤ N ≤ 1000, 0 ≤ M ≤ N(N − 1) / 2, 1 ≤ W_i, L_i ≤ N, W_i ≠ L_i

Sample tests

3 2
2 1
2 3

-1

3 2
1 2
2 3

1

4 3
2 3
3 4
4 2

3