Rank

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type
ACSL Practice 2009

In a tournament of players and games, each game involves 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 players are involved in a "cyclic" order. One example is as follows: player beats player , player beats player , and player in turns beats player . In this case, the relative ranking of these 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 integers and in this order, where is the number of players, and the number of games played. The players are identified by the integers .

There are lines after the first line. Each of the lines contains integers a b s_a s_b representing the result of a game: and are the identifiers of the players, and and are the scores of players and respectively. All scores are non-negative integers less than , 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 are in one cycle, and players in another. Total
2. Players and are involved in a cyclic ordering, whereas players and did not play.
3. There is no cycle in this case.
4. There are cycles: players are involved in one cycle, while players are in another. So players are involved in a cyclic ordering.