Masala #1160

Xotira 256 MB Vaqt 1000 ms Qiyinchiligi 35 %
14

  

O'ta maxfiy parol

Bir noma'lum xaker keyingi contestda muammolarga duch kelmaslik uchun Robocontest test tizimining administrator parolini olmoqchi.  Buning uchun u administratorning kabinetiga yashirincha kirib, lotincha kichik harflardan iborat bo‘lgan n ta paroldan iborat bo‘lgan varaqni o‘g‘irladi.

Xaker uyiga qaytib, Robocontestni buzishga tayyorgarlik ko'ra boshladi.  U tizimda faqat oʻgʻirlangan roʻyxatdagi parollar borligini va tizim a va b parollarining ekvivalentligini quyidagicha tekshirishini aniqladi:

  • a parolda ham, b parolda ham uchrovchi biror bir x harfi mavjud bo'lsa, a va b parollari ekvivalentdir;
  • a va b parollar ekvivalent bo'ladi qachonki ro'yxatda shunday c parol bo'lsaki bunda u a ga ham b ga ham ekvivalent bo'lsa.

Agar tizimda parol o'rnatilgan bo'lsa va tizimga kirish uchun unga tenglashtirilgan parol qo'llanilsa, u holda foydalanuvchi tizimga kiradi.

Masalan, agar ro'yxatda ″i″, ″j″, ″ij″, ″k″ parollari bo'lsa, ″i″, ″j″, ″ij″ parollari bir-biriga ekvivalent, lekin ″k″ paroli ro'yxatdagi boshqa parollarga ekvivalent emas.  Boshqacha aytganda, agar:

  • admin paroli ″j″ bo'lsa, tizimga ushbu parollardan birortasi yordamida kirishingiz mumkin: ″i″, ″j″, ″ij″;
  • admin paroli ″k″ bo'lsa, tizimga faqat ″k″ dan foydalanib kirishingiz mumkin.

Ro'yxatdagi faqat bitta parol test tizimidagi administrator parolidir.  Tizimga kafolatlangan kirish uchun zarur bo'lgan minimal parollar sonini hisoblashda xakerga yordam bering.  Shuni yodda tutingki, xaker tizimda qaysi parol o'rnatilganligini bilmaydi.


Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida \(n\ (1≤n≤2*10^5)\) butun soni mavjud - ro'yxatdagi parollar soni.  Keyingi n qatorda roʻyxatdagi parollar mavjud – boʻsh boʻlmagan \(s_i\) satrlari, uzunligi koʻpi bilan 50 ta harfdan iborat.  Ba'zi parollar o'zaro teng bo'lishi mumkin.

Barcha parollarning umumiy uzunligi \(10^6\) ta belgidan oshmasligi kafolatlanadi.  Ularning barchasi faqat kichik lotin harflaridan iborat.


Chiquvchi ma'lumotlar:

Bitta qatorda parollarning minimal sonini chop eting, ulardan foydalanish tizimga kafolatlangan kirish imkonini beradi.


Misollar
# input.txt output.txt
1
3
ab
bc
abc
1
2
5
yyyyyyyyyyyyyyyyyyyyyyyyyyy
xxxxxx
zz
zzzzzzzzzzz
zzzzzzzzzz
3
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin