A. Угсаатны таавар

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эртний Бэрландчууд нэр урт байх тусам түүний нь чухал гэдэгт итгэдэг байв. Тиймээс Бэрландийн хаад урт нэрээрээ алдартай байв. Гэхдээ урт нэр зарим талаараа тохиромжгүй тул Бэрландчууд хаадынхаа нэрийг товчлохоор шийджээ. Тэд хаадаа нэрийх нь эхний үсгээр дууддаг болсон байна. Тиймээс Victorious Vasily Pupkin хаан үргэлж VVP хэмээн нэрлэгддэг байжээ.

Бэрландад хаадын удам угсаа нэгнийгээ залгамжилсаар ирсэн. Гэхдээ тэд бүгд ерөнхий уламжлалаараа нэгтгэгдсэн байжээ. Бэрландийн уламжлалын дагуу улсаа цэгцтэй байлгахын тулд өв залгамжлагчдийн эхний нэр нь өвөгийнх нь сүүлийн нэртэй адилхан байх хэрэгтэй байв.(тиймээс өв залгамжлагчийн товч нэрний эхний үсэг нь өвөгийх нь товч нэрний сүүлийн үсэгтэй давхцана)Бэрландчууд цэгцтэй байдлыг илүүд үздэг тул энэ уламжлал хэзээ ч зөрчигдөөгүй байна. Мөн Бэрландчуудын өөр нэг уламжлал нь анхний хааний эхний нэр нь сүүлийн хааний сүүлийн нэртэй давхвах ёстой байна.(Тиймээс эхний хааний товч нэрний эхний үсэг сүүлийн хааний товч нэрний сүүлийн үсэгтэй давхцах юм)Энэ уламжлал мөн л байнга мөрдөгддөг.

Угсаатны Нэр нь их энгийн дүрмээр бүтдэг:Хаадын нэрсийг дарааллаар нь бүгдийг нь нэг мөрөнд бичье. Тэгвэл "ab" болон "ba" угсаатны нэр нь "abba" болно, харин гацхан "abca" хаан байгаа бол "abca" гэж нэрлэгдэнэ.

Түүхч Васиа Бэрландын хаадын болон тэдний хамаатнуудын товч нэрсийг олжээ. Бэрланддах угсаатны байж болох хамгийн урт боломжит нэрийг олоход туслаарай.

Сануулж хэлэхэд жагсаалтанд хаадын нэр дарааллаараа бичэгдсэн байгаа. Өөрөөр хэлбэл $A$ хаан нь $B$ хаанаас өмнө хаан байсан бол $A$ хааны нэр жагсаалтанд $B$ хааны өмнө орсон байна.

Оролт

Эхний мөрөнд Васиагийн олсон нэрсийн тоо болох $n$ ($1 ≤ n ≤ 5*10^{5}$) байна. Дараагийн $n$ мөрөнд $n$ товч нэрс байна.(нэг мөрөнд нэг нэр). Товч нэрс нь хоосон биш Латин жижиг үсгүүдээс тогтоно. Мөн урт ни $10$ аас хэтрэхүй.

Гаралт

Олдсон угсаатны товч нэрийн үсгийн тоог хэвлэ.

Хэрэв Васиагийн жагсаалт буруу байвал, ямар ч угсаатан олдохгүй байвал $0$ -ийг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
3
abc
ca
cba
Гаралт
6
Оролт
4
vvp
vvp
dam
vvp
Гаралт
0
Оролт
3
ab
c
def
Гаралт
1

Тэмдэглэл

Эхний жишээнд 2 Угсаатан олдож болно. Эхнийх нь "abcca" (нэг болон хоёрдахь хаад). Дараахь нь "abccba" юм(нэг болон гуравдахь хаад).

Хоёр дахь жишээн дээр Угсаатан олдохгүй юм.

Гурав дахь жишээн дэх цор ганц угсаатан нь нэг хаанаас бүтэх бөгөөд тэр нь "c" юм.

Сэтгэгдлүүдийг ачааллаж байна...