Maximizing Distinct Flower Colors

Megan is planning to pick flowers to make a bouquet. There are n flowers available, each described by its type and color. However, she can only pick at most one flower from each type. From each flower type you may choose any flower available, but note that if two chosen flowers share the same color, they contribute only once to the bouquet’s distinct colors.

Your task is to compute the maximum number of distinct colors that can appear in the bouquet. Formally, let \(T\) be the set of flower types, and for each type \(t\) let \(C_t\) be the set of colors available for that type. You need to select at most one color per type such that the total number of distinct colors is maximized. In other words, you are to find a selection \(\{c_t : c_t \in C_t \text{ for } t \in T'\}\) for some subset \(T' \subseteq T\) with maximum size of \(\bigcup_{t\in T'} \{c_t\}\).

Note: It is possible that different types share some colors, so an optimal selection may require careful reassignments.

inputFormat

The input is read from standard input and has the following format:

n
flower_type_1 flower_color_1
flower_type_2 flower_color_2
...
flower_type_n flower_color_n

Where n is an integer denoting the number of flowers, and each of the next n lines contains two strings representing a flower’s type and its color respectively.

outputFormat

Output to standard output a single integer: the maximum number of distinct colors in the bouquet.

5
rose red
rose yellow
lily white
lily pink
tulip purple

3