Hide

Problem C
Victory Through Synergy

/problems/victorythroughsynergy/file/statement/en/img-0001.png
Johnny has been roped into a fantasy soccer league and needs your help to set up the best team.

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:

  1. If two players are from the same country, a link between the two players will have a synergy score of $1$.

  2. If two players are in the same league, a link between the two players will have a synergy score of $1$.

  3. If two players are on the same team, a link between the two players will have a synergy score of $2$.

  4. 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$.

  5. 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

Please log in to submit a solution to this problem

Log in