近年イズア国では、山から街に降りてくる動物に悩まされている。あなたは動物を山へ帰そうと研究を重ね、以下のことを明らかにした。
あなたは、街に降りてきた動物を、この方法でどのくらい山へ帰すことができるかを計算することにした。
街に降りてきた動物の名前が与えられたとき、この方法で最大いくつのペアを山へ帰すことができるかを求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$ $str_1$ $str_2$ : $str_N$
1行目に動物の数$N$ ($2 \leq N \leq 100,000$)が与えられる。続く$N$行に$i$番目の動物の名前を表す文字列$str_i$が与えられる。ただし$str_i$は英小文字と英大文字で構成された10文字以下の文字列である。また、すべての動物の名前は異なる($i \ne j$なら$str_i \ne str_j$)。
山へ帰すことができる動物のペアの数の最大値を出力する。
4 aedb aeb ebCd cdE
1
4 bcD bD AbD bc
2