Kezdőlap


Feladat:	S.108	Korcsoport: -	Nehézségi fok: -
Füzet:	2016/május, 294. oldal		PDF \| MathML

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

András és Béla egy fa-gráfon játszik, melynek $N$ ( $1 \leq N \leq 100 000$ ) csúcsa van. Összesen $M$ ( $1 \leq M \leq 100 000$ ) lépésből áll a játék. Minden lépés kétféle lehet:

‐	András kiválasztja a fa két csúcsát, és a köztük lévő egyértelmű út minden élére egy csokit helyez.

‐	Béla megkérdezi, hogy egy adott élen hány csoki van.

A feladat: Béla kérdéseit gyorsan megválaszolni.
A program olvassa be a standard input első sorából

N

-et és

M

-et, majd a következő

N - 1

sorból a fa éleit:

u

v

egészeket. Ezután

M

sor következik. Minden sor egy P vagy Q betűvel kezdődik, majd egy

u, v

egész számpár következik. Ez utóbbi számpár egy csúcspárt jelöl. A ,,P'' betű jelentése, hogy András az

(u, v)

csúcsok közti egyértelmű út minden élére tesz egy csokit. A ,,Q'' betű jelentése, hogy Béla megkérdezi, hogy hány csoki van az

(u, v)

élen. A program írja a standard output soraiba a Béla kérdéseire adott válaszokat.

\begin{matrix} Példa bemenet & Példa kimenet: \\ (a sortörések egy részét a példában/jel jelöli): \\ 4 6 / 1 4 / 2 4 / 3 4 & 2 \\ P 2 3 / P 1 3 / Q 3 4 & 1 \\ P 1 4 / Q 2 4 / Q 1 4 & 2 \end{matrix}

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.
Beküldendő egy tömörített s108.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.