DSU#8798

DSU

1 saniyə
64 meqabayt
Asan

Ujlandiyada şəhər var və onlar -dən -ə qədər nömrələnmişdir. Başlanğıcda şəhərlər arasında heç bir yol mövcud deyil. Zaman keçdikcə şəhərlər arasında yollar tikilir.

Turist Vasif sizdən sorğunu cavablandırmağı xahiş edir. Sorğular iki növdə olur:

Giriş

Birinci sətirdə və (1 \le n, q \le 2 \times 10^5) ədədləri verilir.

Növbəti sətirdə sorğular yuxarıda göstərilən formatda verilir.

Çıxış

Hər -ci tip sorğu üçün cavabı ayrı-ayrı sətirlərdə çap edin.

Nümunələr

Nümunə 1

Loading
Loading