Qrafik Dəlilik#4138
Bytelanddə iki əsas video kart istehsalçısı var: Bitotronics və 3D-Bytes. Onların ən qabaqcıl kartları bir-birinə çox bənzəyir. Hər biri, işlənmiş siqnalı ötürən tellərlə birləşdirilmiş bir çox qovşaqdan ibarətdir. Bu kartlar iki növ qovşaqdan ibarətdir: yuvalar və prosessorlar. Tel şəbəkəsi aşağıdakı şərtlərə cavab verir:
Hər bir yuva yalnız bir prosessora və başqa heç bir yuvaya bağlıdır.
Hər bir prosessor ən azı iki digər qovşağa bağlıdır.
Şəbəkədəki hər hansı iki qovşaq arasında onları birləşdirən dəqiq bir tel yolu mövcuddur. Başqa sözlə, qovşaqlar arasındakı əlaqələrin qrafiki ağacdır.
Bitthew kompüter avadanlıqları ilə maraqlanır. O, hər istehsalçıdan bir video kart alıb. Təsadüfən kartların eyni sayda yuvası olduğu üçün, Bitotronics kartının hər yuvasını 3D-Bytes kartının fərqli yuvasına kabellərlə birləşdirməyə qərar verib. Əldə etdiyi cihaz belə görünür:
Bitthew cihazdan maksimum emal gücü əldə etmək istəyir. Bunun üçün, işlənmiş siqnalın keçə biləcəyi bir yol tapmaq istəyir. Yol hər iki kartın hər bir qovşağını dəqiq bir dəfə ziyarət etməli və eyni kartdakı eyni qovşaqda başlayıb bitməlidir. Bitthewə bunun mümkün olub-olmadığını öyrənməyə kömək edin.
Girişin ilk sətri test hallarının sayı T-ni ehtiva edir. Test hallarının təsvirləri aşağıdakı kimidir:
Hər bir test halı üç tam ədəd k, n, m (2 ≤ k ≤ 1000, 1 ≤ n, m ≤ 1000) ilə başlayır ki, bunlar müvafiq olaraq hər kartdakı yuvaların sayını, Bitotronics kartındakı prosessorların sayını və 3D-Bytes kartındakı prosessorların sayını göstərir. Kartlardakı qovşaqlar aşağıdakı kimi adlandırılır:
Bitotronics kartındakı yuvalar: AS1, AS2, ..., ASk
Bitotronics kartındakı prosessorlar: AP1, AP2, ..., APn
3D-Bytes kartındakı yuvalar: BS1, BS2, ..., BSk
3D-Bytes kartındakı prosessorlar: BP1, BP2, ..., BPm
Növbəti n+k−1 sətir Bitotronics kartındakı tel şəbəkəsinin təsvirini ehtiva edir. Bu sətirlərin hər biri həmin kartdakı bir-birinə birbaşa tel ilə bağlı olan iki fərqli qovşağın adlarını ehtiva edir. Təsvir boş sətirlə tamamlanır. Növbəti m+k−1 sətir 3D-Bytes kartındakı tel şəbəkəsinin eyni formatda təsvirini ehtiva edir. Təsvir başqa bir boş sətirlə tamamlanır. Test halının son k sətiri Bitthew tərəfindən əlavə edilmiş kabelləri təsvir edir. Bu sətirlərin hər biri müxtəlif kartlardakı birbaşa kabel ilə bağlı olan iki yuvanın adlarını ehtiva edir. Hər yuva dəqiq bir bu k sətirdə mövcud olacaq. Hər test halından sonra bir boş sətir var, sonuncu istisna olmaqla.
Test hallarına girişdəki ardıcıllıqla cavabları çap edin. Hər test halı üçün bir sətir cavabını çap edin. Əgər istənilən xüsusiyyətlərə malik bir yol yoxdursa, NO çıxış edin. Əks halda, YES yazın və yolun təsvirini verin: siqnalın keçəcəyi sırada n+m+2k fərqli qovşaq. Hər iki ardıcıl qovşaq tel və ya kabel ilə bağlı olmalıdır. Əlavə olaraq, birinci və sonuncu qovşaq bağlı olmalıdır.
Nümunə 1