ACSL Practice 2009

In a tournament of $N$ players and $K$ games, each game involves $2$ players. A player may play any number of games, but in each game his opponent must be a different person. A player needs not play with everybody (it is even possible, though strange, that a player does not play any game at all!). In a game, there is no draw - a player either wins or loses.

After all the games have been played, the players are ranked. There are a few situations where ranking is not possible, but here we are interested only in one particular situation where more than $2$ players are involved in a "cyclic" order. One example is as follows: player $A$ beats player $B$, player $B$ beats player $C$, and player $C$ in turns beats player $A$. In this case, the relative ranking of these $3$ players cannot be determined.

Note that a player may be involved in more than one cyclic ordering; when this happens, the player should be counted only once.

(Since we are only interested in players involved in cyclic ordering, those players whose ranking cannot be determined due to other reasons - for instance, a player who did not play any game at all should not be considered here. See the examples.)

You are given a list of games and their results, and you are to find the total number of players whose ranking cannot be determined due to cyclic ordering.

Input Specification

The first line contains $2$ integers $N$ $(2\le N\le 20)$ and $K$ $(1\le K\le 30)$ in this order, where $N$ is the number of players, and $K$ the number of games played. The players are identified by the integers $1,2,\dots ,N$.

There are $K$ lines after the first line. Each of the $K$ lines contains $4$ integers a b s_a s_b representing the result of a game: $a$ and $b$ are the identifiers of the players, and $s_a$ and $s_b$ are the scores of players $a$ and $b$ respectively. All scores are non-negative integers less than $10$, and the player with the larger score wins.

Output Specification

The output contains an integer which is the number of players whose ranking cannot be determined due to cyclic ordering.

Sample Input 1

10 12
1 8 2 1
1 2 5 0
10 7 1 2
6 9 6 9
3 4 3 1
9 5 3 1
8 2 6 8
4 9 3 0
4 1 5 2
6 10 3 5
3 5 1 9
6 7 9 8

Sample Output 1

7

Sample Input 2

5 3
1 3 9 7
5 1 9 2
3 5 2 0

Sample Output 2

3

Sample Input 3

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

Sample Output 3

0

Sample Input 4

10 5
2 4 0 2
2 6 5 3
8 2 8 2
6 4 6 2
8 6 0 2

Sample Output 4

4

Explanation

1. Players $3,4,5,9$ are in one cycle, and players $6,7,10$ in another. $($Total $=7)$
2. Players $1,3,5$ are involved in a cyclic ordering, whereas players $2$ and $4$ did not play. $(3)$
3. There is no cycle in this case. $(0)$
4. There are $2$ cycles: players $2,4,6$ are involved in one cycle, while players $2,6,8$ are in another. So players $2,4,6,8$ are involved in a cyclic ordering. $(4)$