Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
A game company produced new highprofile car racing game for settop 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 roundrobin 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 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 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.
2 ≤ N ≤ 1000, 0 ≤ M ≤ N(N − 1) / 2, 1 ≤ W_{i}, L_{i} ≤ N, W_{i} ≠ L_{i}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

