E. Ерөнхий өвөг дээдэс

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

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

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

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

Берландын бүх амьд биетүүдийн DNA дараалал нь Латин жижиг үсгүүдээс тогтох хоосон биш мөрөөр дүрслэгдэж болдог байв. Берландын эрдэмтэд бүх амьд биетүүд нь тодорхой үе шатаар дамжин хувьсан өөрчлөгддөг болохыг олж мэджээ. Ямар нэгэн үе шатны турш тухай амьд биетийн DNA мөрийн яг нэг тэмдэгт нь өөр яг 2 ширхэг тэмдэгтээр солигдох юм. Ерөнхийдөө нийт $n$ ширхэг боломжит солилт байх ажээ. $a_{i}$->$b_{i}c_{i}$ гэсэн солилт нь $a_{i}$ гэсэн тэмдэгтийг $b_{i}c_{i}$ гэсэн 2 тэмдэгтээр сольж буйг илэрхийлнэ. Мөн солилт бүр нь хязгааргүй тооны удаа хийгдэж болох юм.

Хэрэв $s_{1}$ болон $s_{2}$ DNA дарааллуудын хувьслын үр дүнгүүд (өөр тооны үе шатаар дамжин үүссэн үр дүнгүүд байж болно) байж болох $s_{3}$ DNA дараалал оршин байвал $s_{1}$ болон $s_{2}$ DNA дарааллуудтай 2 амьд биетийг ерөнхий өвөг дээдэстэй байна гэж үзнэ. Таны даалгавар бол $s_{1}$ болон $s_{2}$ гэж өгөгдсөн DNA дарааллуудтай амьд биетүүд нь ерөнхий өвөг дээдэстэй эсэхийг олох юм. Хэрэв хариулт нь эерэг байвал та хамгийн богино урттай ерөнхий өвөг дээдсийн DNA дарааллыг олно уу.

Оролт

Эхний мөрөнд хоосон биш DNA дараалал $s_{1}$, 2-дахь мөрөнд хоосон биш DNA дараалал $s_{2}$ өгөгдөнө. Эдгээр мөрүүдийн урт нь 50-аас хэтрэхгүй байх бөгөөд зөвхөн Латин жижиг үсгүүдээс тогтсон байна. 3-дахь мөрөнд бүхэл тоо $n$ ($0 ≤ n ≤ 50$) өгөгдөх ба энэ нь боломжит солилтын тоог илэрхийлнэ. Дараагийн $n$ мөрийн мөр болгонд $a_{i}$->$b_{i}c_{i}$ хэлбэртэйгээр боломжит нэг солилтыг дүрсэлсэн байна. $a_{i}$, $b_{i}$ болон $c_{i}$ гэсэн тэмдэгтүүд нь Латин жижиг үсгүүд байх ба $s_{1}$ болон $s_{2}$ мөрүүд нь давхацсан байж болох юм. Түүнчлэн солилтыг агуулсан мөрнүүдэд ижил солилтууд байж болно.

Гаралт

Хэрэв $s_{1}$ болон $s_{2}$ нь ерөнхий өвөг дээдэсгүй бол -1 гэж хэвлэнэ үү. Бусад тохиолдолд $s_{1}$ болон $s_{2}$-ын өвөг дээдсийн DNA дараалал байх хамгийн богино урттай $s_{3}$ дарааллыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
ababa
aba
2
c->ba
c->cc
Гаралт
2
Оролт
ababa
aba
7
c->ba
c->cc
e->ab
z->ea
b->ba
d->dd
d->ab
Гаралт
1
Оролт
ababa
aba
1
c->ba
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...