Meduza
Hər kəsə məlumdur ki, Yagellon Universitetində biz bitkiləri çox sevirik. Ağaclar, meşələr və hətta kaktuslar haqqında yüzlərlə məsələ yaratmışıq! Təəssüf ki, heyvanlar haqqında məsələlər o qədər də məşhur deyil. Bu gün biz sübut etmək istəyirik ki, biz heyvanları da sevirik.
Bir qrafın meduza olması üçün onun sadə, əlaqəli və istiqamətsiz olması, həmçinin zirvə və kənar saylarının bərabər olması lazımdır. Sizə n zirvəli meduza J verilir. Zirvələrin istənilən alt çoxluğu S ⊆ J üçün, əgər hər bir T ⊆ S üçün meduzanın əlaqəli alt qrafı mövcuddursa və bu alt qraf T-dəki bütün zirvələri ehtiva edirsə, həmçinin S-dən başqa heç bir zirvəni ehtiva etmirsə, onda S heyrətamiz alt çoxluq adlanır.
Maksimum mümkün heyrətamiz alt çoxluğun J ölçüsü nə qədərdir?
Giriş Məlumatları
Birinci sətir testlərin sayı z-ni ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri bir tam ədəd n (3 ≤ n ≤ 10^5) - meduzanın zirvələrinin sayını ehtiva edir.
Növbəti n sətir iki tam ədəd u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n ) ehtiva edir - hər biri meduzanın bir kənarına uyğundur. Zəmanət verilir ki, verilmiş qraf meduzadır və hər iki zirvə bir kənardan çox birləşdirilməyib.
Bütün testlərdəki zirvələrin ümumi sayı 10^6-dan çox deyil.
Çıxış Məlumatları
Hər test üçün bir tam ədəd çıxarın - meduzanın maksimum mümkün heyrətamiz alt çoxluğunun ölçüsü.