Demək olar ki, Union-Find
Ümid edirəm ki, Union-Find adlı gözəl məlumat strukturunu tanıyırsınız. Bu tapşırıqda sizdən buna bənzər, lakin tam olaraq eyni olmayan bir strukturu həyata keçirmək tələb olunur.
Yazmalı olduğunuz məlumat strukturu, kəsişməyən çoxluqlar dəstini təmsil edir və üç əməliyyatı dəstəkləyir:
1 p q: p və q-nu ehtiva edən çoxluqları birləşdirin. Əgər p və q artıq eyni çoxluqdadırsa, bu əmri nəzərə almayın;
2 p q: p-ni q-nu ehtiva edən çoxluğa köçürün. Əgər p və q artıq eyni çoxluqdadırsa, bu əmri nəzərə almayın;
3 p: p-ni ehtiva edən çoxluqdakı elementlərin sayını və cəmini qaytarın.
Əvvəlcə n çoxluq dəsti mövcuddur: {1}, {2}, {3}, ..., {n}.
Giriş məlumatları
Bir neçə testdən ibarətdir. Hər bir test iki tam ədəd n və m (1 ≤ n, m ≤ 100000) ehtiva edən bir sətirlə başlayır - tam ədədlərin sayı və əmrlərin sayı. Növbəti m sətirin hər biri bir əmri ehtiva edir. Hər bir əməliyyat üçün 1 ≤ p, q ≤ n. Giriş faylının ölçüsü 5 MB-dan çox deyil.
Çıxış məlumatları
Hər bir 3 tipli əməliyyat üçün iki tam ədəd çıxarın: elementlərin sayı və onların cəmi.
İzah
Əvvəlcə: {1}, {2}, {3}, {4}, {5}
1 1 2 əməliyyatını yerinə yetirdikdən sonra: {1,2}, {3}, {4}, {5}
2 3 4 əməliyyatını yerinə yetirdikdən sonra: {1,2}, {3,4}, {5} (biz {3}-dən 3-ü çıxardıqda yaranan boş çoxluğu nəzərə almırıq)
1 3 5 əməliyyatını yerinə yetirdikdən sonra: {1,2}, {3,4,5}
2 4 1 əməliyyatını yerinə yetirdikdən sonra: {1,2,4}, {3,5}