== include(page="template/taskheader" task_id="bitconnect") ==
Hei hei hei Eddie Valoare a tot căutat o metodă de îmbogăţire rapidă pentru a-şi cumpăra sticle de Tedi pe care să le bea împreuna cu fraţii săi, şi în sfârşit i-a venit o idee garantată succesului: acesta îşi va creea propria criptomonedă(numita junior coin,sau prescurtat jc). Totul a mers bine până când Eddie a trebuit să implementeze crypto currency-ul. Prima provocare a acestuia a fost efectuarea tranzacţiilor.
Hei hei hei Eddie Valoare a tot căutat o metodă de îmbogăţire rapidă pentru a-şi cumpăra sticle de Tedi pe care să le bea împreună cu fraţii săi, şi în sfârşit i-a venit o idee garantată succesului: acesta îşi va crea propria criptomonedă(numită $Junior Coin$,sau prescurtat $JC$). Totul a mers bine până când Eddie a trebuit să implementeze crypto currency-ul. Prima provocare a acestuia a fost efectuarea tranzacţiilor.
Modul de efectuare a tranzacţiilor operează după un model şmenar, care poate fi descris în felul următor:
* fiecare boss are asociat un număr
* între 2 bossi este o favoare frăţeasca dacă and-ul între numerele lor este nenul(între $x$ şi $y$ există o favoare frăţeasca, dacă şi numai dacă $x & y != 0$)
* pentru a efectua o tranzacţie de la $x$ la $y$,se doreşte ca aceasta sa folosească cât mai puţine favoruri frăţeşti; pentru ca favorurile nu sunt ceva uşor de obţinut Eddie ar dori sa ştie care este numărul minim de favoruri prin care trec mai multe tranzacţii. Totuşi, Eddie nu e mulţumit: el ştie ca moneda lui va avea un succes aproape instant, aşadar în final moneda trebuie sa respecte 3 tipuri de operaţii:
** $add(x)$ - bossul $x$ se decide sa se alăture familiei monedei. Intre el şi bossii vechi se formează favoruri frăţeşti. Se garantează ca $x$ nu face parte din familie.
** $erase(x)$ - bossul $x$ a câştigat destulă valoare şi decide sa nu mai investească în moneda. Aşadar el trebuie eliminat şi toate favorurile pe care le avea trebuie şterse.
** $transaction(x,y)$ - Eddie vrea sa afle numărul minim de favoruri folosite pentru a fi efectuata o tranzacţie de la $x$ la $y$,se garantează ca $x$ şi $y$ fac parte din familie.
* între 2 bossi este o favoare frăţească dacă and-ul între numerele lor este nenul (între $x$ şi $y$ există o favoare frăţească, dacă şi numai dacă $x & y != 0$)
* pentru a efectua o tranzacţie de la $x$ la $y$, se doreşte ca aceasta să folosească cât mai puţine favoruri frăţeşti; pentru că favorurile nu sunt ceva uşor de obţinut Eddie ar dori să ştie care este numărul minim de favoruri prin care trec mai multe tranzacţii. Totuşi, Eddie nu e mulţumit: el ştie că moneda lui va avea un succes aproape instant, aşadar în final moneda trebuie să respecte 3 tipuri de operaţii:
** $add(x)$ - bossul $x$ se decide să se alăture monedei. Între el şi bossii vechi se formează favoruri frăţeşti. Se garantează că $x$ nu face parte din monedă.
** $erase(x)$ - bossul $x$ a câştigat destulă valoare şi decide să nu mai investească în monedă. Aşadar el trebuie eliminat şi toate favorurile pe care le avea trebuie şterse.
** $transaction(x,y)$ - Eddie vrea să afle numărul minim de favoruri folosite pentru a fi efectuată o tranzacţie de la $x$ la $y$ sau $-1$ dacă nu se poate efectua o tranzacţie; se garantează că $x$ şi $y$ fac parte din monedă.
Deoarece Eddie ştie că ceea ce cere este prea greu, el va da 2 variante de a raspunde la queryuri:
Deoarece Eddie ştie că ceea ce cere este prea greu, el vă dă 2 variante de a răspunde la queryuri:
* $bit mode$ - trebuie să spuneţi numărul minim de favoruri; aceasta varianta va primi $100%$ din punctaj/test
* $connect mode$ - trebuie să spuneţi doar dacă exista un mod de a efectua tranzacţia de la $x$ la $y$; această variantă va primi $25%$ din punctaj/test
* $bit-mode$ - trebuie să spuneţi numărul minim de favoruri; această variantă va primi $100%$ din punctaj/test
* $connect-mode$ - trebuie să spuneţi doar dacă există un mod de a efectua tranzacţia de la $x$ la $y$; această variantă va primi $25%$ din punctaj/test
h2. Date de intrare
Pe prima linie $Q$, care reprezintă numărul de operaţii.
Pe fiecare din următoarele $Q$ linii va apărea $t$,care reprezinta tipul operaţiei( $1=insert,2=erase,3=transaction$ ), $x$ şi $y$(dacă $t = 3$)
În fişierul de intrare $bitconnect.in$ se va găsi pe prima linie un număr natural N, care reprezintă numarul de operaţii.
Pe următoarele $N$ linii vor apărea operaţiile descrise mai sus în următoarea formă:
h2. Date de ieşire
* $1 x$ - bossul $x$ se alătură reţelei; se garantează că acesta nu era deja în reţea;
* $2 x$ - bossul $x$ iese din reţea; se garantează că acesta era deja în reţea;
* $3 x y$ - se cere răspunsul la întrebarea legată de bossii $x$ şi $y$;
Pe prima linie va apărea modul în care vreţi sa răspundeţi( $bit/connect$ ).
Pe următoarele linii vor apărea răspunsurile operaţiilor de tip 3 fiecare pe câte o linie separata
h2. Date de ieşire
h2. Restricţii si precizari
În fişierul de ieşire $bitconnect.out$ se va găsi pe prima linie cuvântul $"bit"$ (fără ghilimele) în caz că doriţi să răspundeţi în $bit-mode$, altfel se va găsi cuvântul $"connect"$ (tot fără ghilimele).
Pe următoarele linii vor apărea răspunsurile operaţiilor de tip 3 astfel:
*pentru 4% din punctaj raspunsul va fi 0,1,sau -1
*pentru alte 12% din punctaj N <= 2000
*pentru alte 16% din puncta N <= 5000
*pentru alte 20% din punctaj N <= 55000
*pentru restul de 48% din punctaj N <= 105000
*mesajele pe teste sunt:
**TO THE MOON! = OK pentru modul bit
**to the moon!-ish = OK pentru modul connect
**Fisierul de iesire este o teapa = Format incorect la fisierul de iesire
** HODL = Incorrect
* dacă modul ales a fost $bit-mode$, pe fiecare linie se va găsi numărul minim de favoruri folosite pentru a face o tranzacţie între bossii $x$ şi $y$; în caz că nu se poate efectua o tranzacţie între bossii $x$ şi $y$, se va afişa $-1$;
* dacă modul ales a fost $connect-mode$, pe fiecare linie se va găsi $1$ dacă se poate efectua o tranzacţie directă sau indirectă între bossii $x$ şi $y$, altfel se va afişa $0$;
h2. Restricţii si precizari
* $Subtask 1 (testul 1) - 4 puncte: răspunsul va fi 0, 1, sau -1, N ≤ 200$
* $Subtask 2 (testele 2-5) - 16 puncte: N ≤ 500$
* $Subtask 3 (testele 6-13)- 32 puncte: N ≤ 7000$
* $Subtask 4 (testele 14-25)- 48 puncte: N ≤ 106000$
* $La o tranzactie intre x si x se considera ca se folosesc 0 favoruri$
* $Pentru cei neiniţiaţi in arta cryptomonedelor:$
** $"TO THE MOON!" = OK pentru modul bit$
** $"to the moon!-ish" = OK pentru modul connect$
** $"Fisierul de iesire este o teapa" = Format incorect al fişierului de ieşire$
** $"HODL" = Incorect$
* $Valorile numerelor sunt numere naturale mai mici decât 2^62^$
* $Nu întrebaţi ce înseamnă termenii de mai sus de la evaluator, că e posibil să ne supărăm, să luăm punctele şi să nu le mai dăm.$
h2. Exemplu
