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

Ural Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Sumo Tournament

Time limit: 1.0 second
Memory limit: 64 MB
A sumo tournament is held in Tokyo, in which 2N sportsmen take part. In each encounter there is a winner, and the loser drops out of the tournament. Thus, in order to determine the winner of the tournament, it is necessary to conduct N rounds.
The organizers wish that in as many rounds as possible all encounters would be held between sumoists from different prefectures of Japan. For that they can forge the drawing results arbitrarily.


The first line contains the number N (1 ≤ N ≤ 10). Each of the next 2N lines contains the name of a sumouist and the prefecture which he presents. The name and prefecture are sequences of Latin letters of length not exceeding 30.


Output the maximal number of rounds in which sumoists from the same prefecture will not fight each other regardless of the outcomes of encounters (that is, find the maximal possible K such that in at least K rounds all encounters will be between sumoists from different prefectures). The organizers can control the initial arrangement of sportsmen but can't control results of encounters.


Homasho Ishikawa
Tamakasuga Tokyo
Futeno Tochigi
Takekaze Tokyo
Kasugao Yamaguchi
Kotoshogiku Ishikawa
Kotomitsuki Tokyo
Miyabiyama Shizuoka
Problem Author: Sergey Pupyrev
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007
To submit the solution for this problem go to the Problem set: 1551. Sumo Tournament