7. Novodobý farmár

Ako isto viete, nie každá kukurica je rovnaká. Niektoré odrody sú šťavnaté, iné majú zas obrovské obilky. Podaktoré sú dokonca aj dúhové!!! A povedzte mi, kto by už na svojom poli nechcel mať takúto biodiverzitu? Presne takto každoročne rozmýšľa aj Adam. Doteraz to mal pomerne jednoduché, na dedinskej burze vedel za výhodnú cenu jedného Trojkenu vykonať ľubovoľnú z barterových ponúk. Tento rok sa ale Americkým vedcom podarilo nevídané. Dokážu upravovať genetický kód kukurice, skoro úplne, ako sa im zachce¹! Dokonca si otvorili aj pobočku v Adamovej rodnej dedine, Kombajnovských Klasoviciach. Za svoje služby si neúčtujú nič menej ako jeden Trojken. Pomôžte Adamovi zistiť, koľko najmenej Trojkenov musí zaplatiť za to, aby z jeho nudnej odrody kukurice získal nejakú zaujímavejšiu.

Úloha

Každá odroda kukurice sa dá jednoznačne určiť jej genetickým kódom ako reťazec, ktorý sa skladá len z písmen L a R (môže byť aj prázdny). Za jeden Trojken dokáže genetické laboratórium v Kombajnovských Klasoviciach odstrániť gén na konci genetického kódu nejakej odrody alebo pridať na koniec ľubovoľný z génov L a R. Na burze taktiež existuje \(n\) barterových ponúk, ktoré sa vzťahujú na odrody \(a_i\) a \(b_i\). Za vykonanie jednej výmeny zaplatí Adam jednej Trojken a môže vymeniť odrodu \(a_i\) za odrodu \(b_i\) alebo naopak. Adama by zaujímalo \(q\) scenárov, v ktorých začína s odrodou s genómom \(z_i\) a chcel by skončiť s genómom \(k_i\). Zistite, koľko najmenej Trojkenov ho to môže stáť.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(q\) \((0 \leq n \leq 10^3, 1 \leq q \leq 10^4)\) udávajúce počet barterových ponúk na burze a počet scenárov, na ktoré Adama zaujíma odpoveď. V ďalších \(n\) riadkoch sa na každom nachádzajú \(2\) reťazce \(a_i\) a \(b_i\), ktoré hovoria, že odroda s genómom \(a_i\) sa dá vymeniť za odrodu s genómom \(b_i\) za zaplatenie \(1\) Trojkenu a naopak. Nasleduje \(q\) riadkov, na každom z nich sa nachádzajú \(2\) reťazce \(z_i\) a \(k_i\). Pre každý riadok vypíšte, koľko najmenej Trojkenov treba zaplatiť na to, aby Adam z odrody \(z_i\) dostal odrodu \(k_i\).

Všetky reťazce genómov na vstupe sa skladajú len z písmen L a R a obsahujú aspoň jedno písmeno. Existuje ale aj kukurica s prázdnym genómom.

Obmedzenia

Označme si \(D\) najväčšiu dĺžku reťazca na vstupe. Potom pre všetky sady platí, že \((n+q) \cdot D \leq 2 \cdot 10^6\).

V jednotlivých sadách navyše platia nasledujúce obmedzenia:

Keďže je vstup veľmi veľký, odporúčame v jazyku C++ použiť rýchle načítavanie vstupu cin.tie(0)->sync_with_stdio(0) a namiesto endl používať '\n'.

Formát výstupu

Vypíšte \(q\) riadkov, na \(i\)-tom z nich, koľko najmenej Trojkenov treba zaplatiť na to, aby Adam získal zo začiatočnej odrody koncovú.

Príklady

Input:

2 2
R LL
RR RLR
LLL RLR
RRL RLR

Output:

4
2

V prvom scenári jedna z najlacnejších možností môže vyzerať napríklad takto. Najprv odstránime posledný gén, čím dostaneme odrodu LL. Tú dokážeme za jeden Trojken zmeniť za odrodu R. Potom už len stačí pridať postupne gény L a R. Celkovo zaplatíme 4 Trojkeny. V druhom scenári vyzerá najlacnejšia možnosť takto. Najprv odstránime posledný gén a potom vymeníme odrodu RR za odrodu RLR. Takto zaplatíme 2 Trojkeny.

Input:

0 1
LLR LR

Output:

3

Je zbytočné na začiatku pridávať nejaké gény na koniec, keďže neexistujú žiadne barterové ponuky. Preto je optimálne 2-krát odstrániť posledný gén a raz pridať gén R na koniec, čo stojí spolu 3 Trojkeny.