Hər hansı bir narahatçılığa görə üzr istəyirik.
Krakovdakı Yagellon Universitetində təhsil almağın həm üstünlükləri, həm də çatışmazlıqları var. Üstünlüklərdən biri Yagellon Universitetinin özüdür. Çatışmazlıqlara isə Krakovun tramvay yollarının tez-tez yenidən qurulması zərurəti daxildir.
Əvvəlcə, ictimai nəqliyyat şəbəkəsi müəyyən sayda tramvay xətlərindən ibarətdir. Sonra bu xətlərdən biri dayandırılır, sonra digəri və daha biri... Krakovda dəyişməz bir qayda var: bir xətt işə başlamadan əvvəl həmişə bir xətt dayandırılır. Hal-hazırda bütün xətlər hələ dayandırılmayıb və siz tramvayda oturub düşünürsünüz ki, universitetlə birbaşa əlaqəniz yeni itdi. Pəncərədən baxaraq özünüzə sual verirsiniz: "Bu şəhərdə həqiqətən ən bəxtsiz sərnişin mənəm? Yoxsa haradasa daha çox dəyişiklik etməli olan biri var ki, istədiyi yerə çatsın?"
Daha dəqiq desək, B dayanacağı A dayanacağından c dəyişikliklərlə əldə edilə bilər, əgər l[0], ..., l[c] xətləri varsa ki, l[0] A dayanacağını, l[c] isə B dayanacağını xidmət edir və hər bir 0 ≤ i < c üçün l[i] və l[i+1] tərəfindən xidmət edilən müəyyən bir dayanacaq mövcuddur. Siz hər an A və B dayanacaqları arasında c dəyişikliklərlə B-yə gedilə bilən, lakin hər hansı c' < c üçün B-yə gedilə bilməyən bir cüt dayanacaq (A, B) üçün ən böyük c dəyərini bilmək istəyirsiniz.
Qeyd edək ki, bəzən ümumiyyətlə dayanacaqlar arasında keçid etmək mümkün deyil. Yuxarıda göstərilən tərifdən göründüyü kimi, siz bu cütləri analizinizə daxil etməməyi qərara alırsınız - əgər kimsə bu dayanacaqlar arasında keçid etmək istəyirsə, Uber-dən istifadə edəcək.
Giriş məlumatları
Birinci sətir z testlərin sayını (1 ≤ z ≤ 35) ehtiva edir. Sonra testlərin təsviri gəlir.
Hər testin birinci sətiri dayanacaqların sayı n və tramvay yollarının sayı k (2 ≤ n, k ≤ 750) ehtiva edir.
Dayanacaqlar 1-dən n-ə qədər, xətlər isə 1-dən k-ə qədər nömrələnir.
Sonra k sətir gəlir. Bu sətirlərdən i-ci i nömrəli tramvay xəttinin marşrutunu təsvir edir. Hər sətir tam ədəd r[i] (2 ≤ r[i] ≤ n) ilə başlayır, sonra isə r[i] fərqli tam ədəd a[i,j] (1 ≤ a[i,j] ≤ n) gəlir - i-ci tramvay marşrutu tərəfindən xidmət edilən dayanacaqların identifikatorları. Hər hansı bir tramvay xətti hər iki istiqamətdə gedir.
Növbəti sətir bir tam ədəd s (1 ≤ s ≤ k − 1) ehtiva edir.
Sonra s sətir gəlir, tramvay yollarının dayandırılma ardıcıllığını təsvir edir. Bu sətirlərin hər biri bir tam ədəd s[i] (1 ≤ s[i] ≤ k) ehtiva edir - dayandırılmış tramvay xəttinin identifikatoru. Hər hansı bir xətt yalnız bir dəfə dayandırıla bilər.
Bütün testlərdə n və k dəyərlərinin cəmi 1000-dən çox deyil.
Çıxış məlumatları
Hər test üçün s + 1 sətir çıxarın, hər biri bir tam ədəd ehtiva edir. i + 1-ci sətirdə i-ci dayandırma hadisəsindən sonra xətlər arasında ediləcək ən çox dəyişiklik sayını çıxarın (birinci sətir hər hansı dayandırmadan əvvəlki cavabı ehtiva edir).
Qeyd
Əvvəlcə, məsələn, 4 dayanacağından 5 dayanacağına (və ya əksinə) keçmək üçün bir dəyişiklik tələb olunur. Bu keçid 2 marşrutu ilə, sonra 1 marşrutu ilə mümkündür. 2 və ya daha çox dəyişiklik tələb edən dayanacaq cütləri yoxdur.
1 xətti çıxarıldıqdan sonra 1 dayanacağından 3 dayanacağına (və ya əksinə) keçmək üçün iki dəyişiklik tələb olunur.
1 və 4 xətləri çıxarıldıqdan sonra bir-birinə hələ də çata bilən yeganə dayanacaq cütləri (1, 4) və (2, 3)-dür və hər iki halda keçid üçün heç bir dəyişiklik tələb olunmur.
1, 4 və 3 xətləri çıxarıldıqdan sonra bir-birinə çata bilən yeganə dayanacaq cütü (1, 4)-dür. Bu dayanacaqlar arasında keçid üçün heç bir dəyişiklik tələb olunmur.