Hide

Problem N
Vinir

/problems/iceland.vinir/file/statement/is/img-0001.png
Mynd fengin af Pixabay
Benni hefur mjög mikinn áhuga á því hvað fólk á marga vini og eina helgi þegar hann var á skátamóti ákvað hann að skrifa niður hverjir urðu vinir á mótinu. Eins og allir vita þá er vinátta gegnvirk, það er að segja, ef Hannes og Bjarki eru vinir og Bjarki og Arnar eru vinir þá eru Hannes og Arnar líka vinir. Getur þú hjálpað Benna að finna út úr því hvað fólk á marga vini?

Inntak

Fyrsta línan í inntakinu inniheldur tvær tölur $N$, fjöldi skáta á mótinu, og $Q$, fjöldi fyrirspurna. Næstu $Q$ línur innihalda eina fyrirspurn hver. Það eru tvær tegundir af fyrirspurnum, 1 a b stendur fyrir að Benni sá að $1 \leq a \leq n$ og $1 \leq b \leq n$ urðu vinir. Hin tegundin af fyrirspurn er á forminu 2 a sem þýðir að Benni vill vita hversu marga vini $a$ er búinn að eignast á mótinu.

Úttak

Fyrir hverja fyrirspurn af gerðinni 2 a, skrifaðu út eina línu sem segir til um hversu marga vini $a$ er búinn að eignast á mótinu.

Stigagjöf

Hópur

Stig

Takmarkanir

1

20

$1 \leq N,Q \leq 1000$

2

30

$1 \leq N,Q \leq 10^5$, allar vináttutengingar koma á undan öllum fyrirspurnum um fjölda vina.

3

50

$1 \leq N,Q \leq 10^5$

Sample Input 1 Sample Output 1
2 3
1 1 2
2 1
2 2
1
1
Sample Input 2 Sample Output 2
4 5
2 1
1 1 4
2 4
1 3 4
2 3
0
1
2

Please log in to submit a solution to this problem

Log in