problema/chat

chat

Salutare baieti
buna Jordan!
Sugi pula Alin!

== include(page="template/taskheader" task_id="chat") ==
 
Gigel s-a plictisit de ChatGGG şi începe să discute cu prietenii lui din lumea reală, pe o aplicaţie reală de chat. Împreună cu prietenii lui, observă că utilizatorii din fereastra de chat sunt ordonaţi descrescător după activitate, dar utilizatorul curent este tot timpul afişat primul. Ei doresc să testeze dacă lista de utilizatori este afişată corect, aşa că mai mulţi dintre ei se sincronizează şi fac un screenshot al ferestrei de chat simultan, examinând ordinea afişată. Dându-se ordinea observată de $K$ dintre cei $N$ membri ai chat-ului, verificaţi dacă există o ordonare a participanţilor, astfel încât cele $K$ liste afişate să fie consistente. O listă este consistentă dacă toate elementele respectă ordinea descrescătoare a activităţii, cu excepţia primului element, care reprezintă participantul care a realizat screenshot-ul.
 
h2. Date de intrare
 
Fişierul de intrare $chat.in$ conţine pe prima linie numărul de teste $T$. Fiecare test începe cu o linie care conţin numerele $N$ şi $K$, reprezentând numărul total de membri şi numărul de membri care au realizat screenshot-uri. Următoarele $K$ linii conţin ordinea din chat observată de fiecare participant.
 
h2. Date de ieşire
 
În fişierul de ieşire $chat.out$ se va tipări câte o line pentru fiecare test, conţinând textul $DA$, dacă ordinea din cele $K$ liste este consistentă, respectiv $NU$, altfel.
 
h2. Restricţii
 
* $1 ≤ K ≤ N ≤ 50000$
* $1 ≤ T ≤ 50$
 
Participanţii la chat sunt numerotaţi de la $1$ la $N$. Ordinea văzută de fiecare participant este o permutare a mulţimii ${1, 2, ..., N}$.
 
h2. Exemplu
 
table(example). |_. chat.in |_. chat.out |
| 2
  4 3
  1 2 3 4
  2 1 3 4
  4 1 2 3
  4 2
  1 2 3 4
  2 1 4 3
| DA
  NU
|
 
h3. Explicaţie
 
În primul exemplu, ordinea este $1, 2, 3, 4$. Fiecare participant se vede pe el primul, iar restul au ordinea relativă corectă.
În al doilea exemplu, participantul 1 îl vede pe 3 înaintea lui 4, dar participantul 2 îl vede pe 4 înaintea lui 3 - imposibil.
 
== include(page="template/taskfooter" task_id="chat") ==
 

public

task: chat