E. Цэвэрлэгээ

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

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

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

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

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

Санта Клаус өргөн замуудыг харин Элф нарийн замуудыг цэвэрлэх болов. Аль болох цөөн үйлдлээр цэвэрлэгээг хийхийн тулд зам бүрийг цэвэрлэхдээ дараах нөхцөлийг тавьжээ:

  • Дурын хоёр байшингийн хувьд цэвэрлэсэн замуудын тусламжтайгаар нэгээс нь нөгөө рүү нь очих яг нэг энгийн жим байх ёстой.
  • Санта Клаус болон Элф нар яг ижил тооны зам цэвэрлэнэ.

Тэгвэл Санта болон Элф нар тус бүр аль аль замыг цэвэрлэх ёстой вэ?

Оролт

Эхний мөрөнд байшингийн тоо болон замын тоо болох $n$, $m$ ($1 ≤ n ≤ 10^{3}$, $1 ≤ m ≤ 10^{5}$) бүхэл тоонууд байна. Дараагийн $m$ мөр бүрт замаар холбогдсон байшингуудын дугаар болон замын өргөн нарийныг илэрхийлсэн тэмдэгтийг илэрхийлэх $x$, $y$ ($1 ≤ x, y ≤ n$) болон "$M$" эсвэл "$S$" тэмдэгтийн нэг нь байна.( "$M$"-өргөн, "$S$"- нарийн). Зам хоёр чиглэлтэй. Мөн хоёр байшинг хэдэн ч замаар холбосон байж болох юм.

Гаралт

Нөхцөлийг хангахаар замуудыг цэвэрлэх боломжгүй бол "-1" гэж хэвлэ. Боломжтой бол эхний мөрөнд хэдэн зам цэвэрлэгдэхийг хэвлэ. Хоёр дахь мөрөнд цэвэрлэгдсэн замуудын дугаарыг хэвлэ. (Замууд өгөгдөлд буй дарааллаараа $1$-ээс эхлэн дугаарлагдсан гэж үзнэ). Замуудыг ямар ч дарааллаар хэвлэж болно. Дугаар бүр нэг л удаа хэвлэгдсэн байх ёстой. Дугааруудыг хэвлэхдээ зайгаар тусгаарлана.

Орчуулсан: Бат-Од

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

Оролт
1 2
1 1 S
1 1 M
Гаралт
0

Оролт
3 3
1 2 S
1 3 M
2 3 S
Гаралт
2
2 1 
Оролт
5 6
1 1 S
1 2 M
1 3 S
1 4 M
1 5 M
2 2 S
Гаралт
-1

Тэмдэглэл

Цэвэрлэгдсэн замуудын тусламжтайгаар нэг байшингаас өөр байшинд очихдоо зам таарах байшингуудаар байшин бүрээр хамгийн ихдээ нэг удаа дайран өнгөрч байвал энгийн жим гэнэ.

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