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
- Players
are in one cycle, and players
in another.
Total
- Players
are involved in a cyclic ordering, whereas players
and
did not play.
- There is no cycle in this case.
- There are
cycles: players
are involved in one cycle, while players
are in another. So players
are involved in a cyclic ordering.
Comments