B. Лекц

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

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

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

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

Графын онолын хичээлийн шинэ багш маш хурдан ярьдаг. Та түүний лекцийг бичиж тэмдэглэхийн тулд дараах төлөвлөгөөтэй ирсэн.

Та хоёр хэл мэддэг. Профессор эхний лекцээ тавьж байна. Таны мэддэг хоёр хэл хоёулаа Англи жижиг тэмдэгтүүдээс бүрддэг бөгөөд хэл бүр нь ялгаатай хэд хэдэн үгнээс бүрдэнэ. Өөрөөр хэлбэл үг бүр ялгаатай дуудагдана. Түүнээс гадна эдгээр хэлний үгнүүд нь нэгийг харьцах нэг харьцаатай. Энэ нь хэл бүр дээрх үгсийн хувьд нэг үг нь нөгөө хэлний нэг үгтэй ижил утгатай гэсэн үг.

Та профессорын хэлсэн үг бүрийг эхний хэлээр юмуу хоёр дахь хэлээр бичиж чадна. Мэдээж хэрэг та лекцийн туршид аль богино бичигдэх үгтэй хэлийг сонгож үг бүрийг тухайн хэлээр бичнэ. Хэрвээ харгалзах үгнүүд ижил урттай бол та эхний хэлийг илүүд үзнэ.

Танд профессорын тавьж буй лекцийн бичвэр өгөгдсөн байна. Таны тэмдэглэлд лекц хэрхэн бичигдсэн байх вэ?

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n ≤ 3000$, $1 ≤ m ≤ 3000$) бүхэл тоонуудыг агуулах ба эдгээр нь профессорын лекцийн үгийн тоо болон таны мэддэг хэлнүүдийн үгийн тоо юм.

Дараа нь үгнүүд агуулсан $m$ мөрүүд байна. $i$-р мөр нь $a_{i}$, $b_{i}$ тэмдэгт мөрүүдийг агуулах бөгөөд энэ нь $a_{i}$ үг эхний хэлэнд, $b_{i}$ үг хоёр дахь хэлэнд хамаардаг гэсэн утгатай. Мөн эдгээр үгнүүд ижил утгыг илэрхийлнэ. Эдгээр хэлэнд хоёуланд нь байдаг үг байхгүй ба үг бүр яг нэг л хэлэнд тохиолдоно.

Дараагийн мөр нь лекцийн бичвэр болох зайгаар тусгаарлагдсан $n$ ширхэг$c_{1}, c_{2}, ..., c_{n}$ тэмдэгт мөрүүдийг агуулна. $c_{i}$ тэмдэгт мөр бүр нь ${a_{1}, a_{2}, ... a_{m}}$ тэмдэгт мөрүүдийн олонлогт хамаардаг гэдэг нь баталгаатай юм.

Оролт дахь бүх тэмдэгт мөрүүд нь хоосон биш байх ба $10$-с ихгүй Англи жижиг үсгүүдээс бүрдэнэ.

Гаралт

Гаралтанд $n$ ширхэг үг хэвлэнэ. Энэ нь та дэвтэртээ лекцийг хэрхэн бичихийг илэрхийлнэ. Гаралтын үгнүүд оролттой ижил дарааллаар байна.

Орчуулсан: Даариймаа

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

Оролт
4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest
Гаралт
codeforces round letter round
Оролт
5 3
joll wuqrd
euzf un
hbnyiyc rsoqqveh
hbnyiyc joll joll euzf joll
Гаралт
hbnyiyc joll joll un joll
Сэтгэгдлүүдийг ачааллаж байна...