| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 30 | 21 | 20 | 95.238% |
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 losses.
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 ituation 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.
The first line contains 2 integers N (2 ≤ N ≤ 20) and K (1 ≤ K ≤ 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, 3, ..., N.
There are K lines after the first line. Each of the K lines contains 4 integers a b sa sb representing the result of a game: a and b are the identifiers of the players, and sa and sb 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.
The output contains an integer which is the number of players whose ranking cannot be determined due to cyclic ordering.
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
7
The input above represents the results of a 10-player/12-game tournament. Player 1 beats player 8 in game 1, player 1 beats player 2 in game 2, player 7 beats player 10 in game 3, etc. Players 3, 4, 5, 9 are in one cycle, and players 6, 7, 10 in another.
5 3 1 3 9 7 5 1 9 2 3 5 2 0
3
The input describes a 5-player/3-game tournament. Players 1, 3 and 5 are involved in a cyclic ordering, whereas players 2 and 4 did not play.
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
0
The input describes a 5-player/6-game tournament. There is no cycle in this case.
10 5 2 4 0 2 2 6 5 3 8 2 8 2 6 4 6 2 8 6 0 2
4
The input describes a 10-player/5-game tournament. 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 cyclic ordering.