B. Дахин гарч ирэх

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

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

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

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

Жижиг боловч бахархмаар корпорацийн нэр нь Англи цагаан толгойн $n$ жижиг үсгээс бүрддэг. Корпораци дахин гарч ирэхээр шийдсэн буюу идэвхтэй байгаа маркетингийн бодлого нь өөрчлөх хэмжээсүүдийн бүрдэл буюу брэнд (компани болон бараануудын хувьд) эсвэл үүний бүрэлдэхүүн хэсгүүд: нэр, лого, уриа зэргийг агуулж байгаа. Тэд нэрнээс эхлэхээр шийдсэн.

Энэ зорилгынхоо хүрээнд корпораци дэс дараалласан $m$ дизайнеруудыг хөлслөсөн. Нэгэнт корпораци $i$-р дизайнерийг хөлслөсөн учир тэр корпорацийн шинэ нэр үүсгэх ажилд хурдхан дараах байдлаар оролцоно: тэр нэрний хамгийн сүүлийн хувилбарыг авч бүх $x_{i}$ үсгийг $y_{i}$-р солих ба бүх $y_{i}$ үсгийг $x_{i}$-р солино. Энэ нь шинэ хувилбарыг гаргана. Эдгээр үсэгнүүдийн зарим нь тэмдэгт мөрд тохиолдохгүй байх боломжтой. Мөн $x_{i}$ нь $y_{i}$-тай адилхан байж бас болно. Хамгийн сүүлийн дизайнерийн ажлын дараа гарч ирж буй нэрний хувилбар нь корпорацийн шинэ нэр болно.

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

Аркадигийн сэтгэлийн зовиурыг дарж түүнд нэрний эцсийн хувилбарыг хэлж өгнө үү.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 200 000$) байх ба харгалзан анхны нэрний урт ба хөлслөсөн дизайнеруудын тоо байна.

Хоёр дахь мөрөнд Англи $n$ жижиг үсгүүдээс бүрдэх корпорацийн анхны нэр байна.

Дараагийн $m$ мөрөнд дизайнеруудын үйлдлүүдийг тодорхойлно: $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр Англи жижиг үсэг $x_{i}$ ба $y_{i}$ байна.

Гаралт

Корпорацийн шинэ нэрийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6 1
police
p m
Гаралт
molice
Оролт
11 6
abacabadaba
a b
b c
a d
e g
f a
b b
Гаралт
cdcbcdcfcdc

Тэмдэглэл

Хоёр дахь жишээн дээр корпорацийн нэрний дараалласан өөрчлөлтүүд дараах байдалтай харагдана:

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