E. Утасны онол

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

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

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

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

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

Дөрвөлжин ятга нь $n$ мөр ба $m$ баганаас тогтох $n × m$ хэмжээтэй тэгш өнцөгт байна. Мөрүүдийг дээрээс нь доош 1-c $n$ хүртэл дугаарлах бол багануудыг зүүнээс нь баруун тийш 1-с $m$ хүртэл дугаарлана. Тал бүрийн нэгж бүрт зүү байрлуулсан. Ятганы баруун болон зүүн тал тус бүрт $n$ зүү байх ба дээд болон доод тал тус бүрт $m$ зүү байна. Ятга нь ялгаатай хоёр талын ялгаатай хоёр зүүг холбосон яг $n + m$ ширхэг ялгаатай утастай.

Эмускалд анхны дөрвөлжин ятгыг бүтээхийг өөрийн дагалданд даалгасан. Гэхдээ тэр тоглох боломжгүй болох учраас хоёр утас давхардаж болохгүй гэдгийг хэлээгүй. Хэрвээ зүүнүүдийг холбож байгаа хэсгүүд нь давхцаж байвал уг хоёр утсыг давхцаж байна гэж үзнэ. Ятгыг засахын тулд Эмускалд дараах хоёр төрлийн үйлдлийг гүйцэтгэж чадна:

  1. ялгаатай хоёр багана сонгоод утас бүрийг холбож байгаа зүүнүүдийг солихгүйгээр сонгосон багануудын зүүг тал бүрт хооронд нь солих.
  2. ялгаатай хоёр мөр сонгоод утас бүрийг холбож байгаа зүүнүүдийг солихгүйгээр сонгосон мөрүүдийн зүүг тал бүрт хооронд нь солих.

Дараах жишээн дээр хоёр баганыг солих замаар ятгыг зассан байна:

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

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $m$ ($1 ≤ n, m ≤ 10^{5}$) байх ба ятганы өндөр болон өргөний хэмжээ нэгжээр өгөгдөнө. Дараагийн $n + m$ мөр бүрт зайгаар тусгаарласан дөрвөн тэмдэг буюу $a_{i}$, $b_{i}$ хоёр тэмдэгт болон $p_{i}$, $q_{i}$ хоёр бүхэл тоо байна. $a_{i}$, $p_{i}$ нь утасны эхний зүүг тодорхойлох бол $b_{i}$, $q_{i}$ нь хоёр дахь зүүг илэрхийлнэ.

$s$, $x$ хос нь зүүний байрлалыг дараах байдлаар тодорхойлно:

  1. $s$ нь "$L$", "$T$", "$R$" эсвэл "$B$" (хашилтгүйгээр) тэмдэгтүүдийн аль нэгтэй тэнцүү байх ба харгалзан ятганы зүүн, дээд, баруун эсвэл доод талд зүү байрласан гэдгийг илэрхийлнэ.
  2. Хэрвээ зүү ятганы зүүн эсвэл баруун талд байрласан бол $x$ нь мөрийн дугаартай тэнцүү байна, харин ятганы дээд эсвэл доод талд байрласан бол $x$ нь баганын дугаартай тэнцүү байна.

Ямар ч ялгаатай хоёр утас нэг зүүтэй холбогдохгүй.

Гаралт

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

Хэрвээ мөр болон багануудыг солих замаар ятгыг засах боломжгүй бол "$No solution$" (хашилтгүйгээр) гэж хэвлэ.

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

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

Оролт
3 4
L T 1 3
L B 2 2
L B 3 3
T R 1 2
T B 2 1
T R 4 1
B R 4 3
Гаралт
1 2 3 
3 2 1 4 
Оролт
3 3
L T 1 1
T R 3 1
R B 3 3
B L 1 3
L R 2 2
T B 2 2
Гаралт
No solution
Сэтгэгдлүүдийг ачааллаж байна...