E. Толгойлогчийг сонгох сорилт

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

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

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

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

Судлаачид Берландын эртний толь бичгийн хэсгээс олж илрүүлсний ачаар тухайн цаг үеийн тэмдэглэлийг уншиж чаддаг болов. Жишээ нь тэд Берланд овог хэрхэн толгойлогчоо сонгодог байсныг мэджээ.

Хангалттай оролцогчтой болсны дараа нэгэн сорилийг оролцогчдын дунд явуулдаг. Овгийн ахлагч босоо болон хөндлөн зураасаар хуваагдсан нэгэн хөлөг авч (хөлөг нь $N$ мөр болон $M$ баганаас бүрдэнэ) нүд бүрийг хар эсвэл цагаанаар будна. Дараа нь оролцогч бүрт ижил хэмжээтэй бүхэлдээ цагаанаар будагдсан хөлөг өгөгдөнө.

Нэг өдрийн дотор оролцогч хөлгийнхөө ямар нэг талаараа холбогдсон нүднүүдийн олонлогийг ямар нэг өнгөөр будах юм. Хэрэв бүлэгт харьяалагдаж байгаа дурын хоёр нүдний хувьд тэдгээрийг холбох хөрш хоёр нүд бүр нь талаараа холбогдсон, уг олонлогт харьяалагдах зам оршин байвал уг олонлогийг холбогдсон гэж нэрлэнэ. Оролцогч бүрийн зорилго нь өөрийн хавтангаа толгойлогчын хавтантай яг адил байхаар будах ба хамгийн түрүүнд ингэж будсан нь шинэ толгойлогч болох юм.

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

Оролт

Эхний мөрөнд хавтангийн мөр болон баганын тоо болох бүхэл тоонууд $N$ ба $M$ ($1 ≤ N, M ≤ 50$) өгөгдөнө. Дараагийн $N$ мөрөнд мөр бүрт $M$ ширхэг тэмдэгт байх ба энэ нь хавтангын эцсийн будагдсан байдал буюу толгойлогчын хавтан юм. $W$ нь цагаанаар будагдсан нүдийг $B$ нь хараар будагдсан нүдийг илэрхийлнэ.

Гаралт

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

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

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

Оролт
3 3
WBW
BWB
WBW
Гаралт
2
Оролт
2 3
BBB
BWB
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...