ACSL Practice 2009

Task 4: Rank

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

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. 

Output

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

Examples

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

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

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

0

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

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 and 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)

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hi,

My last submission was accepted even though I'm 100% sure it isn't correct. It fails the first example test case. It performs a DFS on the different components of the graph. The code works under the assumption that, if node x is the "parent" of node y, and node y is part of a cycle, then node x is part of a cycle also. This is not correct.

Excuse me if this is an inappropriate place to post this.