Domácí kolo

G: Domino

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Zadání

Karin a Žeňa nemohou do školy, a tak si krátí čas hraním domina. Obě mají šachovnici o velikosti N \times M. Každá z nich pokryla tu svou dominy tak, že všechna políčka jsou zakrytá a žádná domina se nepřekrývají.

Naneštěstí se mohlo stát, že každá pokryla šachovnici jinak, což se jim nelíbí. Rozhodly se, že to opraví. Karin tedy přeskládá domina na své šachovnici tak, aby vypadala stejně jako na šachovnici Ženi. Aby to nebylo tak jednoduché, přidaly slečny následující pravidlo. Jediná operace, kterou může Karin provést, je otočení dvou sousedních domin o 90 stupňů. Pokud se tedy někde nachází dvě domina rovnoběžně vedle sebe a tvoří čtverec, může je Karin otočit. Pomozte jí najít nějakou posloupnost tahů, po které budou obě šachovnice vypadat stejně.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku čísla N a M. Na každém z dalších N řádků je M znaků, které udávají, jak vypadá Karinina šachovnice. Podle toho, jestli na daném políčku leží levá, pravá, horní, nebo dolní polovina domina bude na daném místě znak L, R, U, nebo D.

Následuje prázdný řádek a potom Ženina šachovnice zadaná stejným způsobem za kterou je další prázdný řádek.

Je zaručeno, že vstup odpovídá validnímu pokrytí šachovnic dominy. Speciálně vždy platí, že N \cdot M je sudé číslo.

Tvar výstupu

Za každý problém vypište nejprve počet tahů, které chcete použít a poté na každý následující řádek jeden tah. Tah je dán řádkem a sloupcem levého horního rohu otáčeného čtverce (indexujeme od 1). Maximální délka vašeho řešení je 10^5 tahů; máte zaručeno, že takové řešení vždy existuje. Počet tahů nemusíte minimalizovat, tedy libovolné řešení s nejvýše 10^5 tahy bude uznáno jako správné.

Lehká verze

  • 1 \leq T \leq 100
  • N = 3
  • 2 \leq M \leq 40

Těžká verze

  • 1 \leq T \leq 100
  • 2 \leq N, M \leq 40

Ukázkový vstup

2
3 2
LR
UU
DD

UU
DD
LR

4 4
ULRU
DUUD
UDDU
DLRD

UULR
DDUU
LRDD
LRLR

Ukázkový výstup

2
2 1
1 1
7
2 2
1 2
1 3
3 2
3 1
3 3
2 3

Vysvětlení ukázkového vstupu a výstupu

První vstup by se mohl vyskytnout v lehčí sadě vstupů, druhý ne. Řešení druhého vstupu je znázorněno na následujícím obrázku.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)