Problem B
Absolut bio

cc by-s

Winston jobbar på biografen ”Absolut Bio”, den biograf som är mest topp i hela landet. Salongen har $N$ numrerade platser, och Winstons jobb är att hålla exakt koll på vilka som är lediga och vilka som redan är tagna.

I början av dagen är alla platser lediga. Under dagen sker $Q$ händelser. Besökare ställer sig då och ropar olika önskemål till Winston.

Winston har inte mycket tid på sig, så han måste svara snabbt och korrekt.

När en besökare säger: ”Jag vill sätta mig på plats $i$”, tittar Winston i systemet:

• Om plats $i$ är ledig svarar Winston: ”Ledig” och markerar den som upptagen.

• Annars svarar Winston: ”Upptagen”.

När en besökare säger: ”Jag vill flytta mig från plats $i$ till plats $j$” kontrollerar Winston först plats $j$:

• Om plats $j$ är upptagen svarar Winston: ”Upptagen” och inget ändras.

• Om plats $j$ är ledig flyttar Winston personen: plats $i$ blir ledig och plats $j$ blir upptagen, och han svarar ”Ledig”.

Efter varje fråga måste Winston alltid meddela om den berörda platsen är ledig eller inte. Det är så Absolut Bio håller sin perfekta ordning, och det är framför allt tack vare Winston som biografen fungerar så bra.

Indata

Indatan består av två heltal $N$ ($1 \le N \le 10^{9}$) och $Q$ ($1 \le Q \le 2 \cdot 10^{5}$), antalet sittplatser i salongen och antalet händelser. Alla $N$ platser är lediga från början.

Sedan följer $Q$ rader som beskriver händelser. Varje rad är på något av följande format:

• 1 i, en besökare vill sätta sig på plats $i$ $(1 \le i \le N)$.

• 2 i j, en besökare på plats $i$ vill flytta sig till plats $j$ $(1 \le i, j \le N, i \neq j)$. För varje sådan fråga är det garanterat att plats $i$ är upptagen.

Utdata

För varje händelse ska du skriva ut exakt en rad:

• Skriv Ledig om målplatsen var ledig (och gör ändringen).

• Annars skriv Upptagen.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

I det första exemplet finns det $5$ platser och $3$ händelser:

• En besökare vill sätta sig på plats $1$. Plats $1$ är ledig, så Winston svarar ”Ledig”.

• En besökare vill sätta sig på plats $3$. Plats $3$ är ledig, så Winston svarar ”Ledig”.

• En besökare vill sätta sig på plats $3$. Plats $3$ är upptagen, så Winston svarar ”Upptagen”.

Förklaring av exempelfall 2

I det andra exemplet finns det $5$ platser och $3$ händelser:

• En besökare vill sätta sig på plats $1$. Plats $1$ är ledig, så Winston svarar ”Ledig”.

• En besökare på plats $1$ vill flytta sig till plats $2$. Plats $2$ är ledig, så Winston flyttar personen och svarar ”Ledig”.

• En besökare vill sätta sig på plats $1$. Plats $1$ är ledig (eftersom den tidigare besökaren flyttade sig), så Winston svarar ”Ledig”.

5 3
1 1
1 3
1 3

Ledig
Ledig
Upptagen

5 3
1 1
2 1 2
1 1

Ledig
Ledig
Ledig

10 6
1 2
1 3
1 6
2 6 7
1 10
1 7

Ledig
Ledig
Ledig
Ledig
Ledig
Upptagen

100 10
1 14
1 51
1 93
1 9
1 52
2 9 93
1 14
2 14 93
1 22
2 51 14

Ledig
Ledig
Ledig
Ledig
Ledig
Upptagen
Upptagen
Upptagen
Ledig
Upptagen