Lucky Şəhərlər
John, Cənub-Şərqi Avropa Regional yarışmaları üçün Rumıniyaya gəlib. Bu, onun Rumıniyaya ilk səfəridir və rumınlar ona bir şəhər turu təşkil etməyə qərar veriblər. Tur bir neçə Rumıniya şəhərini əhatə edəcək və hər şəhər yalnız bir dəfə ziyarət ediləcək. John bir şəhərdə başlayacaq və tur boyunca digər şəhərləri ziyarət edərək yenidən başlanğıc nöqtəsinə qayıdacaq.
Ölkədə 1-dən N-ə qədər nömrələnmiş N şəhər və M iki tərəfli yol mövcuddur. Hər yol iki fərqli şəhəri birləşdirir. John üçün bir şəhər turunu düşünün: c_1, c_2, ..., c_n, burada hər bir c_i Rumıniyada bir şəhəri təmsil edir. Bu halda, bütün c_i fərqli olmalıdır və c_i ilə c_{i+1} arasında bir yol olmalıdır, burada i = 1, 2, ..., n-1, həmçinin c_n ilə c_1 arasında da bir yol olmalıdır.
John qəribə bir insandır və tək sayda şəhər ziyarət etmək istəyir. Təşkilatçılar tək sayda şəhərləri əhatə edən bütün mümkün turların planını hazırlayıblar. Şəhər sakinləri Johnun onları ziyarət etməsini arzulayırlar. Beləliklə, əgər bir şəhərdən keçən ən azı bir tur varsa, o şəhər uğurlu adlanır. Sizin vəzifəniz Rumıniyada uğurlu şəhərlərin sayını hesablamaqdır.
Giriş verilənləri
Girişin ilk sətri T - test hallarının sayını göstərən bir tam ədəddir. Hər bir test halı iki tam ədəd ilə başlayan bir sətirdən ibarətdir, bir boşluq ilə ayrılmış - N və M. Sonrakı M sətrin hər biri iki tam ədəd a_i və b_i ehtiva edir, bir boşluq ilə ayrılmış - i-ci yolun birləşdirdiyi şəhərlərin etiketləri.
Məhdudiyyətlər: 1 ≤ T ≤ 77, 0 ≤ N, M ≤ 100000(10^5), 1 ≤ a_i < b_i ≤ N.
Çıxış verilənləri
Çıxış T sətrdən ibarət olmalıdır - hər bir test halı üçün cavablar.