F. Херкуль Пойрот-ын бодлого

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

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

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

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

Өнөөдөр та алдарт Херкуль Пойрот хүртэл илрүүлж чадаагүй нэгэн хэргийг илрүүлэх юм. Алдарт Херкуль Пойрот хүртэл илрүүлж чадаагүй байгаа учраас энэ хэрэг нь одоо хүртэл тодорхой болоогүй ажээ. Мөн уг хэрэг нь хараахан илрээгүй байгаа учраас Агата Кристи-ийн адал явдалт зохиолын номуудад хэзээ ч бичигдээгүй байгаа юм.

Танд ямар хэрэг үйлдэгдсэн болох, хаана хэзээ цогцос олдсон болон бусад мэдээллүүдийг өгөхгүй. Та зөвхөн уг хэрэг нь $n$ өрөө болон хос өрөөнүүдийг хооронд байх $m$ ширхэг хаалгатай нэгэн байшин дотор болсон гэдгийг л мэдэж байв. Байшингийн оршин суугчид нь ихээхэн сэжигтэй байсан ба түүнчлэн бүх хаалганууд нь түлхүүрээр цоожлогдсон байжээ. Мөн бүх түлхүүрүүд нь ялгаатай байв. Өгөгдсөн баримтад үндэслэн Пүрэв гаригийн шөнө байшингийн бүх хаалга цоожлогдсон байсан болохыг түүнчлэн аль өрөөнд оршин суугчид байсан болохыг, тэдгээр оршин суугчдын тус болгонд нь ямар төрлийн түлхүүр байсан болох нь мэдэгдэж байлаа. Баасан гаригийн шөнийн талаар яг ижил зүйлүүд мэдэгдэж байсан бөгөөд бүх хаалганууд нь мөн л цоожтой байжээ. Баасан гаригт маш хүчтэй бороо орж байсан учраас хэн ч байшинг орхиж яваагүй ба хэн ч байшин уруу нэвтэрч ороогүй байв. Өдрийн турш уг байшингийн оршин суугчид нь дараах зүйлсийг хийж болно:

  • Өөрт байгаа түлхүүрүүдийг ашиглан хөрш өрөөнүүдийн хоорондох хаалгыг нээх эсвэл хааж болно (хаалга бүр нь тал болгоноосоо нээгдэж мөн хаагдаж болно);
  • Хэрэв харгалзах хаалга нь нээлттэй байвал өрөөнөөс өрөө уруу хүссэнээрээ орж гарч болох юм;
  • Нэг өрөөнд байгаа оршин суугчид бие биедээ түлхүүрүүд өгч болно.

Херкуль Пойрот-ын "Бяцхан саарал асуудал" нь ийм их хэмжээний мэдээллийг хувилах хангалттай чадваргүй байв. Тэгвэл та Пүрэв гаригийн шөнийн хүмүүсийн байрлал болох түлхүүрүүд тухай мэдээллүүд нь Баасан гаригийн шөнийн нөхцөл байдлыг үүсгэх боломжтой эсэхийг шалгана уу. Хэрэв боломжгүй байвал гэрчүүдийн дунд баттай нэг хүн худал хэлж байна гэсэн үг юм.

Оролт

Эхний мөрөнд харгалзан өрөөний тоо, хаалганы тоо болон байшингийн оршин суугчдын тоог илэрхийлэх 3 бүхэл тоо $n$, $m$ болон $k$ ($1 ≤ n, m, k ≤ 1000$) өгөгдөнө. Дараагийн $m$ мөрөнд хаалгаар холбогдсон хос өрөөнүүдийн дугаарууд өгөгдөнө. Өрөөнүүд нь $1$-ээс $n$ хүртэл дугаарлагдсан байх ба ямар нэгэн хос өрөөний хооронд нэгээс илүүгүй хаалга байрлах юм. Ямар ч хаалга нь өрөөг өөртэй нь холбоогүй байна. Дараагийн $k$ мөрөнд эхний шөнийн оршин суугчдын байрлалуудыг дүрсэлнэ. Мөр болгонд оршин суугчийн нэр ($10$-аас ихгүй Латин үсгүүдээс тогтох хоосон биш мөр байна) өгөгдөх ба нэг хоосон зайны ард өрөөний дугаар мөн нэг хоосон зайны ард уг оршин суугчид байгаа түлхүүрүүдийн тоо өгөгдөнө. Үүний дараа нэг хоосон зайгаар тусгаарлагдсан дугаарууд өгөгдөх ба эдгээр нь уг оршин суугчид байгаа түлхүүрүүдээр онгойлгож болох хаалгануудын дугаарууд байх юм. Хаалганууд нь оролтод өгөгдсөн дарааллаараа $1$-ээс $m$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байна. Мөн бүх оршин суугчид нь ялгаатай нэртэй байх бөгөөд том үсэг болон жижиг үсгүүдийг ялгаатай гэж тооцно уу. $m$ ширхэг түлхүүрүүдийн тус бүр нь оролтод нэг удаа өгөгдөх бөгөөд олон тооны хүмүүс нэг өрөөнд байж болно. Түүнчлэн зарим өрөөнүүд нь хоосон ч байж болох юм. Дараагийн $k$ мөрөнд яг ижил хэлбэрээр 2-дахь шөнийн оршин суугчдын байрлалуудыг дүрсэлнэ. 2-дахь шөнийн тайлбар дээрх оршин суугчдын нэрс нь өөрчлөгдөөгүй хэвээр байх бөгөөд $m$ ширхэг түлхүүрүүдийн тус бүр нь оролтод нэг удаа өгөгдсөн байна.

Гаралт

Хэрэв 2-дахь шөнийн оршин суугчдын байрлалууд нь 1-дэх шөнийн үр дүн байх боломжтой бол "YES" (хашилтгүйгээр) бусад тохиолдолд "NO" гэж хэвлэнэ үү.

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

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

Оролт
2 1 2
1 2
Dmitry 1 1 1
Natalia 2 0
Natalia 1 1 1
Dmitry 2 0
Гаралт
YES
Оролт
4 4 3
1 3
1 2
2 3
3 4
Artem 1 1 4
Dmitry 1 1 2
Edvard 4 2 1 3
Artem 2 0
Dmitry 1 0
Edvard 4 4 1 2 3 4
Гаралт
NO
Сэтгэгдлүүдийг ачааллаж байна...