URI Online Judge | 1902

Association for Consistent Marriages

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

The Association for Consistent Marriages (ACM) asked all people in the country that are single if they were in love and with whom they were in love. Curiously, each single person answered that was in love with exactly one other person, but was shy about declaring these feelings. With this information, ACM wants to form marriages, so people can live happier. If a person A1 is in love with a person A2 and the person A2 is also in love with the person A1, of course ACM can form the marriage {A1, A2}. However, if A1 is in love with A2, but A2 is in love with A3, who is in love with A4… who is in love with Ak, wherein Ak in love with A1, it is also possible to form the marriage {A1, A2, …, Ak}, since recently the polygamic marriage has been approved in Brazil. More formally, ACM can form the marriage {A1, …, Ak} if and only if k ≥ 2, the person Ak is in love with the person A1 and, for every i ∈ {2, …, k}, the person Ai - 1 is in love with the person Ai.

Help ACM to form the largest number of marriages as possible.

Input

The input consists of at most 105 lines and it is ended by end-of-file. Each line of the input consists of the names of two people A and B, indicating that the person A is in love with the person B. Each person's name is a string of at least 1 and at most 10 letters from the Latin alphabet, without diacritics.

Output

Your program shall output a line containing a single integer, representing the largest number of marriages that ACM can form.

Input Samples Output Samples

Carlos Carla
Carla Carlos
Amanda Armando
Armando Artemis
Artemis Amanda

2

Louis Louise
Louise Lucas
Lucas Luke
Luke Louise
Lilica Lucas

1