Полювання за скарбами!#3946
Скрудж МакДак отримав карту стародавнього лабіринту Майядак, наповненого золотом та іншими скарбами. Він знає, що в лабіринті є рівно кімнат, і хоче відвідати всі, щоб зібрати всі багатства. Кожна кімната має рівно один вихід до іншої кімнати. Жодна кімната не має більше одного входу з іншої кімнати. Основна проблема полягає в тому, що немає шляхів між лабіринтом і зовнішнім світом, а також між деякими парами кімнат. Скрудж вирішив скористатися послугами Підрозділу Телепортаційної Компанії Качок, щоб вирішити цю проблему. Він може телепортуватися в будь-яку кімнату всередині лабіринту або назовні. Але є ще одна проблема: кожен стрибок коштує величезну суму грошей, і МакДак повинен мінімізувати кількість телепортацій.
На карті Скруджа кімнати пронумеровані від до , і в кожній кімнаті вказано номер кімнати, куди можна перейти. На жаль, деякі номери пошкоджені через вік і тепер нерозбірливі.
Вам потрібно визначити очікувану суму грошей, яку Скрудж витратить на дослідження всіх кімнат і повернення з лабіринту, за умови, що його стратегія є оптимальною і всі можливі конфігурації лабіринту рівноймовірні. Він починає свою подорож ззовні лабіринту. Перший стрибок Скрудж робить безкоштовно.
На першому рядку введення задано ціле число (0 < T \le 100) — загальна кількість тестових випадків. Кожен тестовий випадок описується двома рядками. На першому рядку є два цілі числа 1 < N \le 4000 — кількість кімнат і 0 \le c \le 1000 — вартість одного стрибка. На другому рядку є чисел, 0 \le a_i \le N — номер кімнати, куди можна піти безпосередньо з -ї кімнати. Якщо номер кімнати нерозбірливий, то a_i = 0. Усі тестові випадки розділені порожнім рядком. Сума у всіх випадках не перевищує . Гарантується, що всі вхідні дані є коректними, тобто існує принаймні один план, що відповідає вхідним даним.
Для кожного вхідного випадку ви повинні вивести одне число з плаваючою комою в окремому рядку — відповідь на задачу з абсолютною або відносною точністю 10^{-6}.
Приклад 1