Problem G. Guaranteed win

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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 Wi Li, meaning that player number Wi won against player number Li. 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 ≤ Wi, Li ≤ N, Wi ≠ Li

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
2 1
2 3

-1
2
3 2
1 2
2 3
1
3
4 3
2 3
3 4
4 2
3

0.047s 0.016s 13