Sosial məsafə saxlanılması
О tələbələr haqqında iki şey demək lazımdır: onlar lazım olandan daha çox iş görməyi sevmirlər və başqalarından uzaq durmağı sevirlər. Birincisi, yəqin ki, şöbənin ağac şəklində təşkil olunmasının səbəbidir (iki dolayı əlaqəli otaq arasında dəhliz tikmək vaxt itkisidir); məhz buna görə də onlar davam edən pandemiya dövründə inkişaf edirlər. İndi sosial məsafə artıq lüks deyil - normadır!
Bununla belə, ağac şəklində binalar və başqalarından uzaq durmaq tamamilə yaxşı bir fikir deyil. Hazırda bəzi otaqlarda k tələbə yaşayır və məsafə siyasətinə görə hər otaqda bir tələbədən çox olmamalıdır. Üstəlik, heç bir iki tələbə birbaşa dəhlizlə əlaqəli otaqlarda yaşamır.
Tezliklə ICPC müsabiqəsi başlayacaq və tələbələr kafedrada səpələnmiş kompüterlərin arxasında yer tutmağa tələsirlər. Bəzi otaqlarda k kompüter var - tələbələr qədər; əlavə olaraq, məsafəni mümkün etmək üçün heç bir iki kompüter eyni otaqda olmamalıdır və birbaşa bir-biri ilə əlaqəli iki otaqda kompüterlər yoxdur. Tələbələr kompüterlərin arxasında istədikləri kimi otura bilərlər, lakin onlar daim sosial məsafəni qorumaq məcburiyyətindədirlər, buna görə də onları lazım olan yerə çatdırmaq çətin, hətta qeyri-mümkün ola bilər.
Siz - ICPC-nin amansız təşkilatçısı və inanılmaz tapşırıqlar dəstinin yaradıcısısınız. Tələbələrin çılğıncasına qaçdığını görərək dəhşətli bir həqiqəti anlayırsınız: əgər tələbələr vaxtında otaqlarına çatmasalar, yarışmada iştirak edə bilməyəcəklər və deməli, həll olunmayan tapşırıqların hazırlanmasına sərf olunan bütün zəhmət boşa gedəcək! Əlbəttə ki, buna imkan verə bilməzsiniz.
Tələbələrin cari mövqeyini və kompüterlərin mövqeyini nəzərə alaraq, hər bir tələbəni kompüter olan otağa köçürən əməliyyatlar ardıcıllığını layihələndirin. Hər belə əməliyyat tələbəni qonşu otağa köçürməlidir; hər əməliyyatdan sonra heç bir iki tələbə eyni otaqda və ya iki qonşu otaqda olmamalıdır. Yarışmanın başlanmasına qalan vaxt sizə 4 * n^2 gedişdən çox olmayan əməliyyatlar etməyə imkan verir, burada n - otaqların sayıdır. Ola bilər ki, tapşırığınız yerinə yetirilə bilməz, lakin bunu öyrənməyin yalnız bir yolu var...
Giriş Məlumatları
Birinci sətir z (1 ≤ z ≤ 10^5) testlərin sayını ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri n (2 ≤ n ≤ 2000) - binadakı otaqların sayını ehtiva edən bir tam ədəddir.
Sonrakı n - 1 sətir iki tam ədəd u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n) ehtiva edir - dəhlizlə birləşdirilmiş iki otaq. Zəmanət verilir ki, təsvir edilən dəhlizlər ağac (dövrəsiz əlaqəli qraf) təşkil edir.
Növbəti sətir bir tam ədəd k (1 ≤ k < n) - tələbələrin (və kompüterlərin) sayını ehtiva edir.
Növbəti sətir s[1], ..., s[k] (1 ≤ s[1] < s[2] < ... < s[k] ≤ n) tam ədədlərini ehtiva edir - tələbələrin başlanğıc mövqeləri.
Növbəti sətir eyni formatda c[1], ..., c[k] tam ədədlərini ehtiva edir, kompüterlərin olduğu otaqları göstərir.
Zəmanət verilir ki, ən azı bir tələbə kompütersiz otaqdadır.
Bütün testlər üzrə n^2 cəmi 4 * 10^7-dən çox deyil.
Çıxış Məlumatları
Hər test üçün tələbələri sosial məsafəni qoruyaraq kompüter olan otaqlara köçürmək mümkün olarsa "YES", əks halda "NO" yazın. Birinci halda, növbəti sətirlərdə istənilən uyğun həlli verin. Həllin təsviri m (1 ≤ m ≤ 4 * n^2) tam ədədi ilə başlamalıdır, bu, gedişlərin sayını göstərir. Sonra hər biri iki tam ədəd a[i], b[i] (1 ≤ a[i] ≠ b[i] ≤ n) ehtiva edən m sətir gəlməlidir, bu, həmin anda a[i] otağında olan tələbənin a[i] ilə dəhlizlə birləşdirilmiş b[i] otağına köçməli olduğunu göstərir.
Həllin uzunluğunu minimallaşdırmağa ehtiyac yoxdur.