Mühafizə#4137
Bytelanddəki ən məşhur rəsm əsəri — Leonardo da Bitci tərəfindən çəkilmiş kompüter siçanı ilə bir xanımın portreti — qorunmalıdır. Bu iş iki dar ixtisaslaşmış laboratoriyada həyata keçiriləcək. Qoruma prosesi bir neçə mərhələyə bölünür və hər mərhələnin hansı laboratoriyada baş tutacağı əvvəlcədən məlumdur.
Çox qiymətli və kövrək olan bu rəsm əsərinin daşınması əlavə risklər yaradır; buna görə də mümkün qədər bundan qaçınılmalıdır. İdeal olaraq, bütün işlər əvvəlcə bir laboratoriyada tamamlanmalı və sonra rəsm digər laboratoriyaya köçürülməlidir. Təəssüf ki, qoruma mərhələləri arasında bəzi asılılıqlar mövcuddur — bəziləri digərləri başlamazdan əvvəl tamamlanmalıdır. Sizin vəzifəniz, rəsm əsərinin laboratoriyalar arasında köçürülmə sayını minimuma endirəcək qoruma mərhələlərinin sıralamasını tapmaqdır. Qoruma hər iki laboratoriyadan birində başlaya bilər.
Girişin ilk sətri test hallarının sayı T ehtiva edir. Test hallarının təsvirləri aşağıdadır:
Hər test halının ilk sətri iki boşluqla ayrılmış tam ədəd n və m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 1000000) — qoruma mərhələlərinin sayı və onların arasındakı asılılıqların sayı. Növbəti sətirdə n boşluqla ayrılmış tam ədəd var — onların i-ci olanı 1dirsə, i-ci qoruma mərhələsi birinci laboratoriyada baş tutacaq, əks halda 2. Növbəti m sətir cüt tam ədəd i, j (1 ≤ i, j ≤ n) ehtiva edir, bu da i-ci mərhələnin j-ci mərhələdən əvvəl tamamlanmalı olduğunu göstərir.
Qoruma mərhələlərini elə sıralamaq həmişə mümkündür ki, bütün asılılıqlar təmin edilsin.
Test hallarının cavablarını girişdə göründüyü sırada çap edin. Hər test halı üçün rəsm əsərinin laboratoriyalar arasında köçürülmə sayının minimumunu ehtiva edən bir sətir çap edin.
Nümunə 1