ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1957. Mundial

Time limit: 1.0 second
Memory limit: 64 MB
Four teams are taking part in football tournament. During this tournament, each team must play one game against every other team. Some of the games have already been played and the results are known. Your task is to determine the possible outcomes of the tournament, assuming that remaining games could have any result (each team can score any non-negative integer number of goals).
After each game, the winning team gets three points and the losing team gets zero points. In case of a draw, both teams get one point. The teams are ranked according to the sum of their points. If two teams have the same number of points, they are ranked by the difference between scored goals s and conceded goals c (the more is sc, the better the rank). If the values of sc are also the same, teams can be ranked either way due to other tie-breaking factors. In the end, each team gets a distinct rank from 1 to 4. Two outcomes of the tournament are different if there is a team which is ranked differently in these outcomes.


The first line of input contains an integer n: the number of games already played (0 ≤ n ≤ 6). Next n lines describe these games. Each game is described by integers a, b, c, d where a and b are the numbers of teams, and c, d are the number of goals scored by team a and team b respectively (1 ≤ a < b ≤ 4; 0 ≤ c, d ≤ 10). It is guaranteed that no two teams played more than one game against each other.


On the first line output an integer m: the number of different possible tournament outcomes. Each of the next m lines should contain four integers: the numbers of teams which get ranks 1, 2, 3 and 4 respectively. The outcomes should be listed in lexicographical order.


1 2 1 0
1 3 2 1
1 4 3 2
2 3 1 0
2 4 5 4
1 2 3 4
1 2 4 3


The first team got nine points, and the second team got six points. The team that wins the last game gets three points and takes the third place. In case of a draw, teams 3 and 4 can be ranked either as 3-rd and 4-th respectively or vice versa.
Problem Author: Mikhail Rubinchik (prepared by Denis Dublennykh)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013