Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Као што сви знамо, врачаре могу да предвиде неке непредвидиве догађаје као што је пролазак неког такмичара на Српску информатичку олимпијаду (СИО). За ту намену користи се СИО стабло.
СИО стабло је дрво у дворишту врачаре Миљане (нико није сигуран зашто се ова чудна биљка не зове СИО дрво). Ово дрво се састоји из \(N\) места гранања, које ћемо звати чворовима, и \(N-1\) грана. Чворови су нумерисани бројевима од \(1\) до \(N\). Наравно, могуће је доћи од сваког чвора до свих других чворова крећући се само по гранама. На свакој грани урезано је по једно слово из скупа \(\{\text{"S", "I", "O"}\}\).
Пар чворова \((U, V)\) је СИО пар ако је на гранама на најкраћем путу (путу који не прелази преко исте гране више пута) између чворова \(U\) и \(V\) свако од слова \(\text{"S"}\), \(\text{"I"}\) и \(\text{"O"}\) урезано исти број пута.
Врачара Миљана тврди да ће на СИО проћи особа која успе да израчуна број СИО парова чворова \((U, V)\) за које важи \(1 \leq U < V \leq N\). Напишите програм који израчунава овај број како бисте проверили да ли је врачара Миљана у праву.
У првом реду улаза налази се један цео број \(N\). У наредних \(N-1\) редова налазе се описи грана. У сваком реду по два цела броја \(U\) и \(V\), и по једно слово из скупа \(\{\text{"S", "I", "O"}\}\), раздвојени размацима.
На излаз испишите број СИО парова чворова \((U, V)\) за које важи \(1 \leq U < V \leq N\).
Тест примери су подељени у 5 дисјунктних група:
6
4 1 S
5 6 O
1 5 I
1 2 S
3 1 S3Парови \((2, 6)\), \((3, 6)\), \((4, 6)\) су СИО парови.