spion

Serviciile secrete din Ţara Crivăţului au o reţea foarte bine pusă la punct. Reţeaua este formată din N centre, numerotate de la $1$ la $N$. Între centre există drumuri ce pot fi parcurse în ambele sensuri, de lungimi cunoscute. Un drum uneşte două centre. Utilizând drumurile existente, între oricare două centre există legătură (directă sau trecând prin alte centre). Distanţa dintre două centre este lungimea totală minimă a drumurilor parcurse pentru a ajunge de la un centru la celălalt.
Şeful Teo a hotărât împărţirea tuturor centrelor în două departamente, de spionaj şi de contraspionaj. O împărţire este considerată optimală dacă maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este minim.
Dacă există mai multe soluţii cu acelaşi maxim, se alege soluţia pentru care diferenţa (în valoare absolută) dintre numărul de centre din departamentul spionaj şi numărul de centre din departamentul contraspionaj este minimă. Dacă şi în acest caz există mai multe soluţii, este preferată prima în ordine lexicografică.

Cerinţă

Dându-se descrierea reţelei, să se scrie un program care să găsească o împărţire optimală a centrelor în două departamente.

Date de intrare

Fişierul de intrare spion.in conţine pe prima linie numerele naturale $N$ şi $M$ reprezentând numărul de centre şi respectiv numărul de drumuri dintre ele. Pe fiecare dintre următoarele $M$ linii vor fi scrise câte trei numere naturale; mai exact, pe linia $i+1$ sunt scrise numerele $a_i \ b_i \ c_i$ cu semnificaţia “există un drum între centrul $a_i$ şi centrul $b_i$ de lungime $c_i$”. Numerele scrise pe aceeaşi linie în fişierul de intrare sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire spion.out va conţine două linii. Pe prima linie va fi scris un număr natural care reprezintă maximul distanţelor dintre două centre din acelaşi departament. Pe cea de a doua linie vor fi scrise $N$ caractere. Caracterul $i$ va fi litera $C$ dacă centrul $i$ va fi în departamentul contraspionaj sau litera $S$ dacă centrul $i$ va fi în departamentul spionaj în împărţirea optimală determinată.

Restricții și precizări

• $2 < N < 101$
• $0 < a_i, b_i \leq N$
• $0 < M, c_i < 16 \ 001$
• Spunem că împărţirea $(x_1, x_2, \dots, x_N)$ precedă din punct de vedere lexicografic împărţirea $(y_1, y_2, \dots, y_N)$ dacă există $k$ astfel încât $x_i = y_i$, pentru orice $i < k$ şi $x_k < y_k$; litera C < litera S.
• Se vor acorda punctaje parţiale după cum urmează:
  • pentru distanţa maximă determinată corect: $20\%$ din punctajul testului respectiv
  • dacă soluţia este corectă (din punctul de vedere al distanţei maxime şi al diferenţei absolute minime), dar nu este prima în ordine lexicografică: $60\%$
  • pentru obţinerea primei soluţii corecte în ordine lexicografică: $100\%$.

Exemplul 1

spion.in

5 4
1 2 1
2 3 1
3 4 1
2 5 7

spion.out

3
CCCCS

Explicație

Maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este $3$.
Diferenţa în valoare absolută dintre numărul de centre din departamentul spionaj şi cel de contraspionaj este $3$.
Soluţia este prima în ordine lexicografică.
O altă soluţie ar fi SSSC, dar aceasta este mai mare lexicografic.

Exemplul 2

spioni.in

5 5
1 3 1
3 2 1
2 5 7
3 4 7
2 4 1

spioni.out

3
CCCCS

Explicație

Maximul distanţelor dintre oricare două centre din cadrul aceluiaşi departament este $3$.
Diferenţa în valoare absolută dintre numărul de centre din departamentul spionaj şi cel de contraspionaj este $3$.