• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

عمو که فردی بسیار پول پرست است، به جاسوسی چند‌جانبه روی آورده.

عمو در $n$ سازمان جاسوسی مختلف عضو است. هر سازمان با دریافت اطلاعات سرّی راجع به سازمانی دیگر، به عمو پول میدهد. عمو نمیتواند یک اطلاعات را به دو سازمان جاسوسی بفروشد، وگرنه این اطلاعات ارزشی نخواهد داشت.

در هریک از $q$ روز گذشته، یک ایمیل حاوی اطلاعات سرّی از فردی ناشناس به دست عمو رسیده است. اگر عمو اطلاعات دو روز پشت سر هم را به دو سازمان مختلف بفروشد، مجبور است از سازمان اول به سازمان دوم برود. میدانیم که عمو طوری این اطلاعات را فروخته که کمترین تعداد جابجایی بین سازمان‌ها را داشته باشد. با دانستن اینکه هریک از اطلاعات ایمیل‌ها مربوط به کدامین سازمان جاسوسی است، بگویید که کمترین تعداد جابجاشدن عمو بین سازمان‌های جاسوسی چقدر است.

ورودی

سطر اول ورودی شامل عدد $n$ است که نمایانگر تعداد سازمان‌های جاسوسی عمو است. سپس در هریک از $n$ سطر بعدی نام یکی از این سازمان‌ها آمده است. نام هر سازمان با دیگری متفاوت است. هر نام میتواند شامل چند کلمه باشد که هریک از حروف کوچک یا بزرگ انگلیسی و اعداد تشکیل شده اند.

سطر بعدی ورودی شامل عدد $q$ است که نمایانگر تعداد ایمیل‌های رسیده به دست عمو است. در $i$مین سطر از $q$ سطر بعدی نام سازمانی آمده است که اطلاعات ایمیل $i$م مربوط به آن است.

$$2 \le n \le 100$$ $$0 \le q \le 1000$$

خروجی

در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین تعداد جابجاشدن عمو بین سازمان‌های جاسوسی است.

مثال

ورودی نمونه ۱

3
KGB
Central Intelligence Agency
Central Intelligence Agency 2
6
KGB
Central Intelligence Agency
Central Intelligence Agency
Central Intelligence Agency 2
Central Intelligence Agency 2
KGB

خروجی نمونه ۱

1

عمو میتواند اطلاعات 3 روز اول را به Central Intelligence Agency 2 بفروشد و سپس به Central Intelligence Agency رفته و اطلاعات 3 روز بعدی را به آن ها بدهد.