A. Нэрсүүдийн харгалзаа

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

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

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

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

Програмчлалын зуны сургалтын багш сурагчиддаа Хоббит кинон дээр гардагтай адил нэрс оноож тэднийг хөгжөөхөөр шийджээ. Сурагч бүр өөрийн нэртэйгээ хамгийн адилхан байхаар шинэ нэртэй болох ёстой. Шинэ нэр бүр тухайн зохиолын ямар нэг баатрын нэр байх ёстой ба одоо багш нэрсүүдийг харгалзуулаад их завгүй байгаа аж.

Зуны сургалт $n$ сурагчтай. Багш тэдэнд зориулж яг $n$ шинэ нэр сонгоно. Сурагч бүр яг нэг шинэ нэр авна. $b$ гэсэн шинэ нэр болон $a$ гэсэн сурагчийн нэрийг авч үзье. $a$ болон $b$-ийн хамгийн урт ерөнхий угтварын уртыг эдгээр нэрсийн хоорондын холбоо гэж нэрлэе. Энэхүү утгыг $lcp(a, b)$ гэж тэмдэглэе. Мөн бид тухайн харгалзааны чанар гэдгээр нэрсүүдийн харгалзаануудын хоорондын холбоонуудын нийлбэрийг ойлгоно.

Чанар нь хамгийн их байхаар нэрсүүдийг харгалзуулна уу.

Оролт

Эхний мөрөнд сурагчдын тоог илэрхийлэх $n$ ($1 ≤ n ≤ 100 000$) гэсэн бүхэл тоо байна.

Дараагийн $n$ мөрөнд хүүхдүүдийн нэрс байна. Нэр бүр хоосон биш Англи цагаан толгойн жижиг үсгүүдээс тогтоно. Зарим нэрс давтагдсан байж болно.

Сүүлийн $n$ мөрөнд өгөгдсөн шинэ нэрсүүд байна. Шинэ нэр бүр хоосон биш Англи цагаан толгойн жижиг үсгүүдээс тогтоно. Зарим шинэ нэрс давтагдсан байж болно.

Сурагчдын нэрс болон шинэ нэрсүүдийн нийт урт $800 000$ аас хэтрэхгүй урттай байна.

Гаралт

Эхний мөрөнд боломжит хамгийн их харгалзааны чанарыг хэвлэнэ.

Дараагийн $n$ мөрөнд хамгийн их чанар бүхий харгалзааг дүрслэх ёстой. Мөр бүрт $a$ дугаарын хүүхэд $b$ дугаарын шинэ нэртэй байвал зохихыг илэрхийлэх $a$ $b$ ($1 ≤ a, b ≤ n$) тоонуудыг зайгаар тусгаарлан хэвлэ.

Харгалзаа нь харилцан нэгэн утгатай байх ёстой буюу гаралтанд сурагчдын нэр болон шинэ нэрс яг нэг нэг удаа хэвлэгдсэн байх ёстой. Хэрэв хамгийн олон боломжит зөв харгалзаа байвал аль нэгийг нь хэвлэ.

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

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

Оролт
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel
Гаралт
11
4 1
2 5
1 3
5 2
3 4

Тэмдэглэл

Эхний жишээний хувьд харгалзаа нь дараахь байдалтай байна:

  • bil-l → bil-bo ($lcp = 3$)
  • gal-ya → gal-adriel ($lcp = 3$)
  • gen-nady → gen-dalf ($lcp = 3$)
  • to-shik → to-rin ($lcp = 2$)
  • boris → smaug ($lcp = 0$)
Сэтгэгдлүүдийг ачааллаж байна...