Omida Smith s-a apucat din nou de colorat. De data aceasta s-a gândit să încerce cu grafuri neorientate cu N noduri etichetate de la 1 la N şi M muchii numerotate de la 1 la M.
La o plimbare, Smith porneşte din nodul etichetat cu 1, se plimbă pe muchiile grafului, după care se întoarce în nodul de plecare.
Astfel, drumul parcurs de Smith începe şi se termină cu nodul 1, poate trece de mai multe prin acelaşi nod şi de asemenea poate trece de mai multe ori prin aceeaşi muchie.
Muchiile grafului sunt iniţial colorate în alb, iar la fiecare trecere a omizii peste o muchie aceasta îşi schimbă culoarea: din albă devine roşie şi din roşie devine albă.
Fiecărui drum îi corespunde astfel o colorare finală a muchiilor, pe care vom numi configuraţie posibilă şi o vom reprezenta ca un şir de M elemente reprezentând în ordine culorile finale ale muchiilor (A pentru alb şi respectiv R pentru roşu).
Omida a observat că din toate configuraţiile posibile, nu toate sunt frumoase. Există unele muchii ′speciale′ care nu arată bine decât dacă au o anumită culoare.
Smith vrea să dea lovitura pe piaţa de grafuri de artă, aşa că generează pentru un graf dat toate configuraţiile frumoase posibile în ordine lexicografică. Va lansa pe piaţă cea de a K-a configuraţie generată, configuraţiile fiind numerotate începând cu 1.
Cerinţă
Scrieţi un program care să determine cea de a K-a configuraţie frumoasă posibilă, în ordine lexicografică.
Date de intrare
Pe prima linie a fişierului de intrare bcolor.in se vor afla numerele naturale N, M, K separate prin câte un spaţiu. Pe următoarele M linii se vor afla descrierile muchiilor grafului.
Pe linia i+1 se va afla descrierea muchiei i, formată din 3 numere naturale x, y, z separate prin câte un spaţiu. Numerele x şi y reprezintă nodurile care sunt extremităţile muchiei, iar z este un număr care poate lua valorile cu semnificaţia de mai jos: z=0 muchia nu este specială z=1 muchia este specială, trebuie neapărat colorată în alb z=2 muchia este specială, trebuie neapărat colorată în roşu.
Date de ieşire
Fişierul de ieşire bcolor.out va conţine o singură linie formată din M caractere din mulţimea {A, R} reprezentând în ordine culorile muchiilor din cea de a K-a configuraţie frumoasă posibilă pentru graful din fişierul de intrare.
Restricţii
1 ≤ N, M ≤ 200
1 ≤ K ≤ 108
Există minim K configuraţii frumoase posibile pentru graful dat.
Muchiile din fişierul de intrare sunt distincte.