B. Графыг будах

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

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

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

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

Танд $n$ орой $m$ ирмэгээс бүрдэх чиглэлгүй граф өгөгдсөн. Эхэндээ ирмэг бүр улаан эсвэл хөх өнгөөр будагдсан байна. Ээлж бүрт тоглогч нэг орой авч уг оройруу чиглэсэн бүх ирмэгийн өнгийг солино. Уг орой дээр төгсгөлтэй бүх улаан өнгөтэй ирмэгүүдийн өнгө хөх болох бол бүх хөх ирмэгүүдийн өнгө улаан болно гэсэн үг.

Бүх ирмэгийн өнгийг ижил болгоход шаардлагтай үйлдлүүдийн хамгийн бага тоог ол.

Оролт

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

Дараагийн $m$ мөрөнд ирмэгүүдийн тодорхойлолт байх ба $i$-р мөрөнд хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$) байх буюу $i$-р ирмэгээр холбогдсон оройнуудын дугаар байна мөн тэмдэгт $c_{i}$ () байх буюу ирмэгийн анхны өнгө байна. Хэрвээ $c_{i}$ нь '$R$' байвал энэ ирмэгийн анхны өнгө улаан байна. Харин $c_{i}$ нь '$B$'байвал энэ ирмэгийн анхны өнгө хөх байна гэсэн үг. Энэ графд өөррүүгээ чиглэсэн холболт болон давхар ирмэг байхгүй.

Гаралт

Хэрвээ бүх ирмэгийн өнгийг ижил өнгөтэй болгох зам байхгүй бол нэг мөрөнд $ - 1$-г хэвлэ. Бусад тохиолдолд эхлээд энэ зорилгыг биелүүлэхэд шаардагдах хамгийн бага үйлдлүүдийн тоо $k$-г хэвлэ. Тэгээд $k$ бүхэл тоон утгууд $a_{1}, a_{2}, ..., a_{k}$-г хэвлэх ба энд $a_{i}$ нь $i$-р үйлдэлд ашиглагдсан оройн дугаар байна.

Хэрвээ хэд хэдэн боломжит хамгийн тохиромжтой үйлдлүүдийн дарааллууд байвал алийг нь ч хэвлэж болно.

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

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

Оролт
3 3
1 2 B
3 1 R
3 2 B
Гаралт
1
2 
Оролт
6 5
1 3 R
2 3 R
3 4 B
4 5 R
4 6 R
Гаралт
2
3 4 
Оролт
4 5
1 2 R
1 3 R
2 3 B
3 4 B
1 4 B
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...