Qrafikin Altı#6223
Qraf nəzəriyyəsindən aşağıdakı (standart) təriflərdən istifadə edəcəyik. qeyri-boş və sonlu bir çoxluq olsun, onun elementləri taclar (və ya düyünlər) adlanır. E \subseteq V \times V olsun, onun elementləri kənarlar adlanır. Onda G = (V, E) istiqamətli qraf adlanır.
müsbət tam ədəd olsun və p = (e_1, \ldots, e_n) uzunluğu olan e_i \in E kənarlarının bir sırası olsun ki, e_i = (v_i, v_{i+1}) (v_1, \ldots, v_{n+1}) taclarının bir sırası üçün. Onda qrafında v_1 tacından v_{n+1} tacına bir yol adlanır və deyirik ki, v_{n+1} v_1-dən əldə edilə bilər, bunu (v_1 \to v_{n+1}) kimi yazırıq.
Burada bəzi yeni təriflər var. G = (V, E) qrafında bir düyünü sink adlanır, əgər -dən əldə edilə bilən hər bir düyünü üçün də -dən əldə edilə bilər.
Qrafın dibi, yəni sink olan bütün düyünlərin alt çoxluğudur, yəni [ bottom(G) = { v V w V: (v w) (w v) }. ]
Sizin vəzifəniz müəyyən qrafların dibini hesablamaqdır.
Giriş bir neçə test halını ehtiva edir, hər biri istiqamətli qraf -yə uyğundur. Hər bir test halı G = (V, E) qrafının taclarının sayını göstərən tam ədəd ilə başlayır, burada taclar V = \{1, \ldots, v\} çoxluğundakı tam ədədlərlə müəyyən ediləcək. Siz 1 \le v \le 5000 olduğunu qəbul edə bilərsiniz. Bundan sonra qeyri-mənfi tam ədəd və sonra cüt tac identifikatorları v_1, w_1, \ldots, v_e, w_e gəlir ki, bu da (v_i, w_i) \in E mənasını verir. Bu cütlərdən başqa heç bir kənar yoxdur. Son test halı sıfırla tamamlanır.
Hər bir test halı üçün müəyyən edilmiş qrafın dibini bir sətirdə çıxarın. Bunun üçün sink olan bütün düyünlərin nömrələrini tək boşluq simvolu ilə ayrılmış şəkildə sıralı qaydada çap edin. Əgər dib boşdursa, boş sətir çap edin.
Nümunə 1