İndiana Cons və Uduzulmuş Futbol Kuboku

1930-cu ildə Uruqvayda ilk dünya futbol çempionatı keçirildi və Uruqvay dramatik finalda Argentina üzərində qələbə qazanaraq kuboku əldə etdi. Bu hadisə çoxdan baş vermiş kimi görünür və indi bu tarixi çempionat ətrafında bir çox miflər və əfsanələr dolaşır. Bəziləri hətta iddia edir ki, Uruqvaya təqdim olunan orijinal kubokun mistik gücü var və bu güc hər hansı bir komandaya dünya çempionatını qazanmaq imkanı verə bilər.

İllər keçdikcə bu orijinal kubok itmişdir və onun mistik gücü yəqin ki, sadəcə bir nağıldır, lakin o, hələ də muzeydə yer almalı olan əhəmiyyətli bir artefaktdır. Onun bərpası üçün mütəxəssis tələb olunur.

Məşhur arxeoloq və macəraçı İndiana Cons bu çətin vəzifəni öz üzərinə götürərək kuboku tapmaq üçün Uruqvaya yola düşdü. Axtarışları onu qədim yeraltı mağara sisteminə apardı, burada kubokun gizlədildiyi ehtimal olunur. Bu mağaralarda çoxlu tələlər var və yalnız onun instinkti və sadiq qamçısı İndini təhlükədən xilas etdi. İndi o, sirli böyük qapılara çatıb və düşünür ki, kubok bu qapıların arxasında gizlənmişdir. Təəssüf ki, qapılar bağlıdır.

Qapılar düymələr və qollarla doludur və onların hamısı hərflər və rəqəmlərlə işarələnib. Qapılar yalnız düymələr və qollar düzgün ardıcıllıqla istifadə edildikdə açılacaq, lakin diqqətli olun! — Çünki kimsə səhv ardıcıllıqla hərəkət etsə, onu təhlükə gözləyir.

Xoşbəxtlikdən, mağaraları araşdırarkən İndi bir neçə şifrəli ipucu tapdı ki, bu da düzgün ardıcıllığı göstərir. Onlardan biri belədir: "Doğru inananlar bilirlər ki, $X$ $O$-dan əvvəl gəlir". Və daha biri: "Heç bir halda $a$-ya toxunmaq olmaz, əgər $b$ hərəkət etməyibsə"! Aydındır ki, bu ipuçları düzgün ardıcıllığı göstərir, lakin burada çoxlu düymələr və qollar, həmçinin çoxlu ipuçları var. İndinin köməyə ehtiyacı var!

İndinin topladığı bütün ipuçları ilə, ona qolların və düymələrin düzgün ardıcıllığını müəyyən etməyə kömək edə bilərsənmi ki, o, macərasını uğurla başa vura bilsin? Amma diqqətli olun — İndi bəzi ipuçlarını qaçırmış ola bilər; ya da bəlkə də, o, bəzi ipuçlarını səhv başa düşüb. Birinci halda, çox güman ki, bir neçə mümkün ardıcıllıq qalacaq, ikinci halda isə ümumiyyətlə mümkün ardıcıllıq olmayacaq. Bu halları aşkar etməli və İndini xəbərdar etməlisiniz.

Giriş verilənləri

Birinci sətir testlərin sayını $t(t\le 30)$ ehtiva edir. Hər bir test üçün qapılardakı $n(1\le n\le 10^4)$ düymələr/qolların sayı və İndinin aşkar etdiyi $h(0\le h\le 10^5)$ ipuçlarının sayı olan bir sətir var. Sonra hər bir ipucu üçün $h$ sətir gəlir, burada $a$ və $b(1\le a,b\le n,a\ne b)$ rəqəmləri göstərir ki, $a$ qolu $b$ qolundan əvvəl çəkilməlidir.

Çıxış verilənləri

Hər bir test üçün $1$-dən $n$-ə qədər olan rəqəmlərin düzgün ardıcıllığını bir sətirdə çıxarın. Əgər mümkün ardıcıllıq yoxdursa, recheck hints çıxarın. Əgər bir neçə mümkün ardıcıllıq varsa, missing hints çıxarın.

Nümunələr