İki Ən Uzun Yol
Tekuhp turistik bir şəhərdir. Şəhərdə N kəsişmə mövcuddur və bunlar M tək istiqamətli yollarla birləşdirilib. Hər tək istiqamətli yol bir kəsişmədən digərinə bağlanır. Bir cüt kəsişməni birləşdirən bir çox yol ola bilər. Şəhəri daha maraqlı etmək üçün yollar elə qurulub ki, hər hansı bir kəsişmədən başlayıb, yollar boyunca səyahət edərək başlanğıc kəsişməsinə qayıtmaq mümkün deyil. (Tekuhp sakinlərinin hər gün işdən evə necə qayıtdığı qəribə bir sirr olaraq qalır.)
Şəhəri ziyarət etməyi planlaşdıran iki turist qrupu var. Onlar bəzi kəsişmələrdən digərinə yollar boyunca səyahət etmək istəyirlər. Lakin, hər iki qrup bir-birinə rast gəlmək istəmir. Beləliklə, onlar iki yol P_1 və P_2 istəyirlər, hər bir P_i üçün, 1≤ i ≤ 2, bəzi kəsişmədən s_i başlayır və kəsişmədə t_i bitir, belə ki, hər iki yol heç bir kəsişməni paylaşmır, başlanğıc və son kəsişmələr də daxil olmaqla. Lakin, mümkündür ki, bir yol P_i yalnız bir düyün ehtiva etsin, yəni s_i = t_i.
Turistlər həmçinin çoxlu yerləri ziyarət etmək istəyirlər. Siz yaxşı bir planlaşdırıcı olduğunuz üçün, hər iki yolda kəsişmələrin ümumi sayını maksimum etmək istəyirsiniz.
Giriş verilənləri
Girişin ilk sətri T (1 ≤ T ≤ 10) tam ədədini, test halların sayını ehtiva edir. Bundan sonra T test halları gəlir.
Hər test halı N və M (1 ≤ N ≤ 300; 1 ≤ M ≤ 3000) tam ədədləri ilə başlayır, burada N kəsişmələrin sayını və M yolların sayını göstərir. Kəsişmələr 1 -dən N -ə qədər nömrələnib. Bundan sonra M sətir, yol əlaqəsini təsvir edir. Hər sətir kəsişmə A -dan kəsişmə B -yə tək istiqamətli yol olduğunu göstərən iki tam ədəd A və B ehtiva edir.
Çıxış verilənləri
Çıxış T sətir ehtiva etməlidir, hər test halı üçün bir sətir. Hər test halı üçün, çıxış iki kəsişməyən yolda maksimum kəsişmə sayını göstərən tam ədəd L ehtiva edir.