Determine how many football kits are needed so that every player can be assigned a shirt and shorts of the right colors.
Football Kit
You are given the number of players and, for each player, the colors of the shirt and shorts they need. A kit consists of one shirt and one pair of shorts.
A shirt or pair of shorts can be used by at most one player. Players can only be assigned items of the exact required color.
Your task is to determine the minimum number of kits that must be prepared so that every player can receive both items they need.
In other words, for every color, if shirt[color] players need a shirt of that color and shorts[color] players need shorts of that color, then the number of kits needed for that color is the maximum of those two counts. Sum this over all colors.
Input Format
- The first line contains an integer
n— the number of players. - The next
nlines contain two integerss_iandt_i, the colors of the shirt and shorts needed by thei-th player.
Output Format
Print a single integer — the minimum number of football kits required.
Constraints
1 <= n <= 1000- Color values are positive integers.
- A color may appear many times in either position.
Example 1
Input
4 1 2 1 3 2 2 3 2
Output
4
Explanation
Color 1 needs 2 shirts and 1 pair of shorts, so 2 kits. Color 2 needs 1 shirt and 3 pairs of shorts, so 3 kits. Color 3 needs 1 shirt and 1 pair of shorts, so 1 kit. But each player contributes one shirt-color and one shorts-color need; the total minimum kits is the sum over colors after matching counts, which here is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.