Get a job P24891


Statement
 

pdf   zip

thehtml

A job placement service at your university handles summer stages of students in commercial companies. This year, there is a set of students requesting a job, and several companies offering exactly one job. After evaluating all the curricula, the job placement service has a list of the companies that are willing to hire each student. The director of this service wishes to know the maximum number of jobs that can be filled.

Input

Input consists of several cases. Every case begins with the number of students n, followed by n lines with the offers for each student, with exactly the format shown in the sample input. Some students can receive offers from every company, but the average number of offers per student is “small”. All student names and company names are different alphanumeric strings. Overall, there are at most n company names. Assume 1≤ n≤ 1000.

Output

For each case, print the maximum number of jobs that can be filled.

Public test cases
  • Input

    6
    Austin : Adobe Apple10 HP
    Bob : Adobe Apple10 Yahoo
    Carol : HP IBM Sun
    Dave : Adobe Apple10
    Eliza : IBM Sun Yahoo
    Frank : HP Sun Yahoo
    10
    A : Z X
    H : P S T
    I : N Z X
    B : Z X
    J :
    E : Y
    C : Z Q R S K
    D : Z S
    F : P S
    G : Z N
    

    Output

    6
    8
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++
    User solutions
    C++