Xəzinə Axtarışı!
Scrooge McDuck qədim Mayaduck labirintinin qızıl və digər xəzinələrlə dolu xəritəsini əldə edib. O, labirintdə dəqiq n otaq olduğunu bilir və bütün sərvəti toplamaq üçün bu otaqların hamısını ziyarət etmək istəyir. Hər otaqdan başqa bir otağa çıxış var və hər otağa başqa bir otaqdan ən çox bir giriş mövcuddur. Əsas problem odur ki, labirint ilə xarici dünya arasında və bəzi otaq cütləri arasında yollar yoxdur. Scrooge bu vəziyyəti həll etmək üçün Duck Teleportation Company Unit-dən istifadə etməyə qərar verir. O, labirintin içindəki və ya xaricindəki istənilən otağa teleportasiya edə bilər. Lakin başqa bir problem də var: hər teleportasiya böyük miqdarda pul tələb edir və McDuck teleportasiyaların sayını minimuma endirməlidir.
Scrooge’un planında otaqlar 1-dən N-ə qədər nömrələnib və hər otaqda hansı otağa gedilə biləcəyini göstərən otaq nömrəsi yazılıb. Təəssüf ki, bəzi nömrələr yaşlanma səbəbindən oxunmaz vəziyyətdədir.
Sizin vəzifəniz Scrooge’un bütün otaqları araşdırmaq və labirintdən çıxmaq üçün lazım olan gözlənilən pul miqdarını tapmaqdır. Onun strategiyası optimaldır və labirintin bütün mümkün konfiqurasiyaları bərabər ehtimallıdır. O, səyahətinə labirintin xaricindən başlayır və etdiyi ilk teleportasiya pulsuzdur.
Giriş verilənləri
Girişin ilk sətrində tam ədəd T (0 < T ≤ 100) verilir — testlərin ümumi sayı. Hər bir test iki sətirlə təsvir olunur. Birinci sətirdə iki tam ədəd 1 < N ≤ 4000 — otaqların sayı və 0 ≤ c ≤ 1000 — bir teleportasiyanın dəyəri. İkinci sətirdə N ədəd, 0 ≤ a_i ≤ N — birbaşa gedilə bilən otaq nömrəsi verilir. Hər hansı bir otaq nömrəsi oxunmazdırsa, a_i = 0. Bütün testlər boş sətirlə ayrılır. Bütün hallarda N cəmi 4000-i keçmir. Bütün giriş halları doğrudur, yəni giriş məlumatlarına uyğun ən azı bir plan mövcuddur.
Çıxış verilənləri
Hər bir giriş halı üçün problemi 10^{-6} dəqiqliklə həll edən bir ondalık nömrəni ayrı sətirdə çıxarmalısınız.