h2. Cerinţă

Se dau $Q$ întrebări de forma $x y$  – unde $x$ şi $y$ sunt două noduri din arbore. Se cere să se răspundă pentru fiecare intrebare dacă $(x, y)$ este LCA palindrom sau nu. Spunem că $(x, y)$ e LCA palindrom dacă:

Se dau $Q$ întrebări de forma $x y$  – unde $x$ şi $y$ sunt două noduri din arbore. Se cere să se răspundă pentru fiecare intrebare dacă $(x, y)$ este **LCA-palindrom** sau nu. Spunem că $(x, y)$ e **LCA-palindrom** dacă:

# Drumul de la $x$ la $LCA (x, y)$ şi drumul de la $y$ la $LCA (x, y)$ au aceeasi lungime.
# Şirul de caractere corespunzător lanţului de la $x$ la $y$, care trece prin $LCA (x, y)$ să fie palindrom.

* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 500.000$
* Pentru teste în valoare de $25$ de puncte $N ≤ 1.000$ şi $Q ≤ 5.000$

* Pentru teste în valoare de $65$ de puncte $N ≤ 20.000$ şi $Q ≤ 100.000$

* Pentru teste în valoare de $60$ de puncte $N ≤ 20.000$ şi $Q ≤ 100.000$
* Se garanteaza ca pentru fiecare query nodurile sunt distincte.

* Problema va fi evaluată pe teste în valoare de $90$ de puncte
* Se vor acorda $10$ puncte din oficiu