İxrac üçün qiymətləndirmə
Luka coğrafi məlumatlar şirkətinə rəhbərlik edir. Bu şirkət şəhərin ətraflı xəritəsini hazırlayır və məlumatları maraqlı tərəflərə təqdim edir. Çox vaxt müştərilərə tam xəritə lazım olmur. Bunun əvəzinə, onlara yalnız əsas küçələri əhatə edən sadələşdirilmiş bir xəritə lazımdır.
Şəhərin xəritəsi n kəsişmədən ibarət olan istiqamətsiz bir qrafdır. Bu kəsişmələr 1-dən n-ə qədər tam ədədlərlə işarələnmişdir və m ikitərəfli küçələrdən ibarətdir. Hər küçəyə mənfi olmayan tam ədəd şəklində bir prioritet təyin edilir. Xəritə sorğusu zamanı müştəri bir prioritet həddi p seçir. Sonra ilkin xəritə kopyalanır və aşağıdakı prosedurdan istifadə edilərək ixrac edilən xəritəyə çevrilir:
Prioriteti p-dən aşağı olan bütün küçələr silinir.
Hər bir kəsişmə i üçün 1, 2, ..., n (göstərilən sırada işlənir):
(a) Əgər kəsişmə i heç bir küçə ilə birləşmirsə, o zaman o silinir.
(b) Əgər kəsişmə i yalnız x və y küçələri ilə birləşirsə və bu küçələr i-dən fərqli a və b kəsişmələrinə aparırsa, o zaman kəsişmə i aşağıdakı şəkildə sıxılır:
x və y küçələri silinir.
Kəsişmə i silinir.
a və b kəsişmələrini birləşdirən yeni z küçəsi əlavə edilir.
95 prioritet həddi ilə ikinci nümunənin təsviri
Əvvəlcə xəritədə döngələr (kəsişməni öz-özünə birləşdirən küçə) və paralel kənarlar (eyni kəsişmə cütü arasında bir neçə küçə) yoxdur, lakin sıxılma proseduru zamanı döngələr və paralel kənarlar yarana bilər. Qeyd edək ki, yuxarıdakı 2. (b) addımında nə x, nə də y döngə ola bilməz (həm a, həm də b i-dən fərqli olmalıdır), lakin yeni əlavə edilən z küçəsi döngə ola bilər (mümkündür ki, a və b eynidir).
Verilmiş xəritə və ixrac sorğuları ardıcıllığı üçün, hər bir sorğu üçün ixrac edilən xəritədə kəsişmələrin və küçələrin sayını tapın.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 300 000) və m (1 ≤ m ≤ 300 000) - kəsişmələrin və küçələrin sayını ehtiva edir. Növbəti m sətirin hər biri üç tam ədəd a, b və p (1 ≤ a, b ≤ n, 0 ≤ p ≤ 300 000) ehtiva edir, bu da a və b kəsişmələrini birləşdirən prioriteti p olan küçəni təsvir edir. Heç bir küçə kəsişməni öz-özünə birləşdirmir. Hər bir kəsişmə cütü arasında yalnız bir küçə mövcuddur.
Növbəti sətir ixrac sorğularının sayı q (1 ≤ q ≤ 300 000) ehtiva edir. Növbəti sətir q tam ədəd ehtiva edir. k-cı ədəd t[k] (0 ≤ t[k] ≤ 300 000) k-cı sorğu üçün hədd dəyəridir.
Çıxış məlumatları
q sətir çıxarın. k-cı sətirdə k-cı sorğu üçün ixrac edilən xəritədə kəsişmələrin və küçələrin sayını göstərən iki tam ədəd çıxarın.