Rezolvare PBinfo #4404

Cerința

RAU-Gigel își amintește cu nostalgie de momentele sale de început într-ale programării, când mai făcea și stângăcii cum ar fi să declare un nume de tipul int…. așa a apărut următoarea problemă:

Să ne imaginăm harta politică a lumii viitorului, împărțită în țări ale căror nume sunt de fapt numere naturale nenule. Între ele există anumite relații: două țări sunt înfrățite dacă au în compunerea numelui lor aceleași cifre (nu contează numărul de apariții), în timp ce două țări se află în conflict dacă nu au nicio cifră comună în numele lor.

Interesat de politică, RAU-Gigel ar vrea să afle câteva informații:

• întrebare de tipul 1: câte țări sunt izolate din punct de vedere politic, în sensul că nu sunt înfrățite cu nicio altă țară?
• întrebare de tipul 2: pentru fiecare țară dintr-o listă de țări preferate să se afle: cu câte țări este înfrățită și cu câte în conflict?

Ajutați-l pe RAU-Gigel să afle răspunsul la cele două tipuri de întrebări ale sale !

Date de intrare

Fișierul de intrare conflicte.in conține pe prima linie tipul T al întrebării, cu valorile 1 sau 2.

Daca T = 1, pe rândurile următoare sunt numele țărilor de pe hartă, adică numere naturale nenule distincte două câte două, dispuse câte unul pe rând, sau mai multe pe rând și separate prin câte un spațiu, în total N numere.

Daca T = 2, pe următorul rând se află un număr natural nenul reprezentând numărul Q de țări preferate, apoi, separate printr-un spațiu, țările respective. Pe rândurile următoare este lista țărilor, ca la taskul 1.

Date de ieșire

Dacă întrebarea e de tipul 1, fișierul de ieșire conflicte.out va conține un sigur rând pe care se află un singur număr reprezentând răspunsul la întrebarea de tipul 1.

Dacă întrebarea e de tipul 2, fișierul de ieșire conflicte.out va conține Q rânduri: pe fiecare rând i se vor afla câte două numere separate printr-un spațiu, reprezentând numărul de țări înfrățite, respectiv în conflict cu țara a i-a din fișierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 100.000, 1 ≤ Q ≤ 1.000, Q ≤ N
• Teste în valoare de 40 puncte conțin o întrebare de tipul 1
• Teste în valoare de 20 puncte conțin o întrebare de tipul 2 și N ≤ 1.000, Q ≤ 10
• Numele țărilor sunt numere naturale nenule, au între 1 și 9 cifre (inclusiv) și nu conțin zerouri nesemnificative (la stânga)
• Țările de pe hartă sunt distincte două câte două; la întrebările de tip 2, lista țărilor preferate ale lui RAU-Gigel nu conține duplicate și este inclusă în lista țărilor de pe hartă
• O țară aflată în conflict cu o altă țară poate să fie izolată din punct de vedere politic, în sensul că nu are aliați
• Toate țările care au în compunerea numelui lor același set de cifre formează o alianță

Exemplul 1:

conflicte.in

1
1133 1356789
3131 13
1331 2444 
678 42 133

conflicte.out

2

Explicație

Pentru întrebarea de tipul 1 avem: țările 1133, 3131, 13, 1331 și 133 formează o alianță, țările 2444 și 42 formează o altă alianță, în timp ce 1356789 și 678 sunt izolate din punct de vedere politic.

Exemplul 2:

conflicte.in

2
2 13 1356789
1133 1356789
3131 13
1331 2444 
678 42 133

conflicte.out

4 3
0 2

Explicație

Pentru întrebarea de tipul 2 avem: țara 13 este înfrățită cu 4 țări: 1133, 3131 și 1331, 133.
Țara 13 este în conflict cu 3 țări: 2444, 678 și 42.
Cea de-a doua țară preferată a lui RAU-Gigel, țara 1356789 nu este înfrățită cu nicio altă țară, dar este în conflict cu țările: 2444 și 42.