Korporativ Şəbəkə
Çox böyük bir korporasiya öz korporativ şəbəkəsini inkişaf etdirir. Əvvəlcə korporasiyanın N müəssisəsinin hər biri, 1-dən N-ə qədər nömrələnmiş, öz hesablama və telekommunikasiya mərkəzini təşkil etdi. Tezliklə xidmətlərin yaxşılaşdırılması üçün korporasiya bəzi müəssisələri klasterlərdə toplamağa başladı, hər biri tək bir hesablama və telekommunikasiya mərkəzi tərəfindən xidmət edilən. Korporasiya mövcud mərkəzlərdən birini I (klaster A-ya xidmət edən) və digər klasterdə B (mütləq mərkəz deyil) olan müəssisələrdən birini J seçdi və onları telekommunikasiya xətti ilə birləşdirdi. Müəssisələr I və J arasındakı xəttin uzunluğu |I – J|(mod 1000). Beləliklə, iki köhnə klaster yeni klasterdə birləşir, köhnə klaster B-nin mərkəzi tərəfindən xidmət edilir. Təəssüf ki, hər bir birləşmədən sonra müəssisəni xidmət edən mərkəzə bağlayan xətlərin uzunluqlarının cəmi dəyişə bilər və son istifadəçilər yeni uzunluğun nə olduğunu bilmək istəyirlər. Şəbəkənin təşkilindəki dəyişiklikləri izləyən və hər an istifadəçilərin suallarına cavab verə bilən bir proqram yazın.
Giriş verilənləri
Proqramınız bir neçə test halını həll etməyə hazır olmalıdır. Girişin ilk sətri yalnız test halların sayı olan T ədədini ehtiva edəcək. Hər bir test N müəssisəsinin sayı ilə başlayacaq (5 ≤ N ≤ 20000). Sonra bəzi sayda sətirlər (ən çox 200000) aşağıdakı əmrlərdən biri ilə davam edəcək:
E I - həmin anda müəssisə I-dən xidmət edən mərkəzə qədər olan yolun uzunluğunu soruşmaq;
I I J - xidmət edən mərkəz I-nin müəssisə J-yə bağlandığını bildirmək.
Test halı O sözünü ehtiva edən sətirlə bitir. I əmrləri N-dən azdır.
Çıxış verilənləri
Çıxış, bütün test hallarında E əmrlərinin sayı qədər sətir ehtiva etməlidir və hər biri - müvafiq müəssisəni xidmət edən mərkəzlə birləşdirən xətlərin uzunluqlarının soruşulan cəmi olan tək bir ədəd.