Problem J
Victory Through Synergy
He has a list of $10$ players that are on his fantasy team (no goalkeepers in this league). He also knows what country they’re from, what league they play in, and what team they play for.
He doesn’t know much about soccer, but he does know these things:
-
If two players are from the same country, a link between the two players will have a synergy score of $1$.
-
If two players are in the same league, a link between the two players will have a synergy score of $1$.
-
If two players are on the same team, a link between the two players will have a synergy score of $2$.
-
If two players are from the same country and in the same league, a link between the two players will have a synergy score of $2$.
-
If two players are from the same country and on the same team, a link between the two players will have a synergy score of $3$.
A team can only be in one league and no two teams will have the same name unless they are the same team.
He has to place the players on his team into a formation of $10$ nodes which can be represented as an undirected graph. The illustration shows the first sample. Therefore, Johnny has to place a player in each node of the graph. Given a particular formation and the members of Johnny’s team, output whether it is possible for Johnny to organize his team to get a perfect team.
A team is a perfect team if and only if every player is placed on a node with a synergy score that is greater or equal to the node’s degree. A node’s degree is the number of links to which it is linked in the formation. A player placed on a node in the formation derives synergy from all players placed on nodes to which the player is linked in the formation. Thus, a node’s synergy score is the sum of the synergy scores of all links to which the node is connected.
Input
The input will contain a single test case. The first line of the input will have one integer $c$ ($0 \leq c \leq 45$). $c$ represents the number of edges in the formation. The next $c$ lines represent the connections between nodes represented as two integers $a$ ($0 \leq a < 10$) and $b$ ($0 \leq b < 10$), where $a$ is not equal to $b$. Then, the next $10$ lines will be the players on Johnny’s team. Each line will contain four strings in the following order: player name, nation, league, team, which are delimited by a single space. These strings are guaranteed to be non-empty and consist of up to $15$ alphanumeric characters, which includes lower- and uppercase English letters, digits, and hyphens.
Output
If a perfect team can be organized by Johnny, print yes. Otherwise, print no.
| Sample Input 1 | Sample Output 1 |
|---|---|
15 0 1 1 2 2 3 0 4 1 5 2 6 3 7 4 5 5 6 6 7 4 8 5 8 6 9 7 9 8 9 Griezmann France LaLiga AtleticoMadrid Benzema France LaLiga RealMadrid Ntep France Ligue1 StadeRennais Sissoko France PremierLeague Spurs Tolisso France Ligue1 Lyon Diarra France Ligue1 OM Evra France CalcioA Juventus Koscielny France PremierLeague Arsenal Varane France LaLiga RealMadrid Sagna France PremierLeague ManCity |
yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
15 0 1 1 2 2 3 0 4 1 5 2 6 3 7 4 5 5 6 6 7 4 8 5 8 6 9 7 9 8 9 PlayerA France A1 A1-1 PlayerB France B1 B1-1 PlayerC France C1 C1-1 PlayerD France D1 D1-1 PlayerE France E1 E1-1 PlayerF France F1 F1-1 PlayerG France G1 G1-1 PlayerH France H1 H1-1 PlayerI France I1 I1-1 PlayerJ Germany J1 J1-1 |
no |
