Штралер sırası
Geologiyada çay sistemi istiqamətli qraf şəklində təsvir edilə bilər. Çayın hər bir hissəsi bir kənar kimi göstərilir; kənarın istiqaməti çayın axını istiqaməti ilə eynidir. Zirvələr çayların mənbələri (məsələn, göl və ya çay), çayların birləşmə və ya ayrılma nöqtələri və ya çayların mənsəbləri olur.
Ştraler Sırası çay sisteminin aşağıdakı şəkildə hesablanır:
Mənbə zirvəsinin sırası 1-ə bərabərdir.
Hər bir digər zirvə üçün, axın yuxarısında yerləşən bütün düyünlər arasında ən böyük sıra i olsun. Əgər bu düyünlərdən yalnız biri i sırasına malikdirsə, onda cari zirvə də i sırasına malikdir. Əgər axın yuxarısında iki və ya daha çox düyün i sırasına malikdirsə, onda cari zirvənin sırası i + 1-ə bərabərdir.
Bütün çay sisteminin sırası mənsəb zirvəsinin sırasına bərabərdir. Göstərilən nümunədə çay sisteminin yalnız bir mənsəbi var. Ştraler Sırası üçə (3) bərabərdir.
Düzbucaqlıdakı rəqəm - Ştraler Sırası. Dairədəki rəqəm - zirvənin nömrəsidir.
Verilmiş çay sisteminin sırasını müəyyən edəcək bir proqram yazın.
Ən böyük sıraya malik real çay - Amazon çayıdır, onun sırası 12-dir. ABŞ-da ən böyük sıraya malik çay - Missisipi çayıdır, onun sırası 10-dur.
Giriş məlumatları
Birinci sətir testlərin sayı t (1 ≤ t ≤ 1000) ehtiva edir. Hər bir test digərindən müstəqil olaraq işlənməlidir.
Hər bir test bir neçə sətirdən ibarətdir. Hər bir testin birinci sətri üç təbii ədəd k, m və p (2 ≤ m ≤ 1000) ehtiva edir. k - testin nömrəsidir. m - qrafda zirvələrin sayı, p - kənarların sayı. Sonra p sətir gəlir, hər biri qrafın bir kənarını təyin edir. Sətir iki təbii ədəd a və b ehtiva edir, bu da suyun a-dan b-yə axdığını göstərir (1 ≤ a, b ≤ m). m zirvəsi çayın mənsəbidir, onun çıxan kənarları yoxdur.
Çıxış məlumatları
Hər bir test üçün bir sətir çıxarın. Orada testin nömrəsini, boşluq və çay sisteminin sırasını çıxarın.