Хиасат недавно зарегистрировал новый аккаут на сайте NeckoForces и, как только его друзья об этом узнали, каждый из них захотел, чтобы его имя было названием хендла профиля Хиасата.
К счастью для Хиасата, он может менять свой профиль в некоторые моменты времени. Также он знает моменты времени, когда его друзья будут заходить на его страницу. Формально, дана последовательность событий двух видов:
- \(1\) — Хиасат может поменять свой хендл.
- \(2\) \(s\) — друг \(s\) посещает профиль Хиасата.
Друг \(s\) будет счастлив, если каждый раз, когда он посетит страницу Хиасата, его хендл будет равен \(s\).
Хиасат просит вас помочь ему, выясните наибольшее количество счастливых друзей, которого можно добиться.
Выходные данные
Выведите одно целое число — наибольшее число счастливых друзей.
Примечание
В первом примере, оптимально поменять хендл на «motarack» в первом событие и на «light» в четвёртом. Таким образом, «motarack» и «light» будут счастливы, а «mike» — нет.
Во втором примере можно выбрать «alice», «bob» или «tanyaromanova», и ровно этот друг и будет счастлив.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1
2 motarack
2 mike
1
2 light
|
2
|
|
2
|
4 3
1
2 alice
2 bob
2 tanyaromanova
|
1
|