Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Mint tudjuk, a jósok előre látnak olyan kiszámíthatatlan eseményt, mint például egy versenyző továbbjutását a Szerbiai Informatikai Olimpiára (SzIO). Erre a célra SIO fát használnak.
A SIO fa Miljana jósnő udvarában található furcsa növény. Ezen a fán \(N\) elágazás (amelyeket csomópontnak nevezünk), és \(N-1\) ág található. A csomópontok számozása \(1\)-től \(N\)-ig megy. Természetesen bármely csomóponttól bármelyik csomópontig eljuthatunk az ágakon haladva . Minden ágon az \(\{\text{"S", "I", "O"}\}\) halmaz egy eleme van bevésve.
Az \((U, V)\) csomópontpár akkor SIO pár, ha az ágakon, amelyeken keresztül a legrövidebb úton haladva az \(U\) és \(V\) között, vagyis egyik csomópontból a másikba (miközben ugyanazon az ágon nem haladhatunk át többször) az \(\text{"S"}\), \(\text{"I"}\)és \(\text{"O"}\) betűk ugyanannyiszor jelennek meg.
Miljana azt állítja, hogy az SzIO-ra az jut tovább, aki ki tudja számolni az \((U, V)\) csomópontok által alkotott SIO párok számát, amelyekre érvényes, hogy \(1 \leq U < V \leq N\). Írjatok programot amely kiszámítja ezt a számot, hogy leellenőrizzétek, Miljana jósnőnek igaza volt-e!
A bemenet első sorában egyetlen egész szám, \(N\) áll. A következő \(N-1\) sorban az ágak leírása található. Minden sorban két egész szám, \(U\) és \(V\), valamint egy betű az \(\{\text{"S", "I", "O"}\}\) halmazból egy-egy szóközzel elválasztva.
A kimenetre kiíratni az \((U, V)\) csomópontok által alkotott SIO párok számát, amelyekre érvényes, hogy \(1 \leq U < V \leq N\).
A tesztpéldák 5 független csoportba oszthatók:
6
4 1 S
5 6 O
1 5 I
1 2 S
3 1 S3A \((2, 6)\), \((3, 6)\), \((4, 6)\) csomópontok SIO párok.