Астероїдні Рейнджери#3387

Астероїдні Рейнджери

3 секунди

256 мегабайтів

Легка

Рік $2112$ , і людство підкорило Сонячну систему. Корпус космічних рейнджерів розмістив бази на кожному придатному для життя астероїді. Ваша задача як члена Міністерства зв'язку астероїдів полягає в тому, щоб забезпечити зв'язок між усіма базами астероїдів космічних рейнджерів з мінімальними витратами. Ви могли б встановити прямі лінії зв'язку між кожною парою баз, але це було б надзвичайно дорого. Замість цього ви хочете встановити мінімальну кількість зв'язків, щоб кожна база могла надсилати повідомлення всім іншим, можливо, через одну або більше проміжних баз. Вартість будь-якої лінії зв'язку прямо пропорційна відстані між двома базами, які вона з'єднує, тому це не здається надто складною задачею.

Однак існує одна невелика складність. Астероїди мають тенденцію рухатися, тож дві бази, які зараз дуже близькі, у майбутньому можуть бути далекими. Тому з часом вам доведеться змінювати зв'язки, щоб завжди мати найдешевшу систему зв'язку. Зміна цих зв'язків вимагає часу і грошей, тому вас цікавить, скільки разів доведеться виконувати таку зміну.

Деякі припущення спрощують ваше завдання. Кожен астероїд вважається однією точкою. Астероїди завжди рухаються лінійно з постійною швидкістю. Жоден астероїд ніколи не стикається з іншими астероїдами. Також будь-яка система зв'язку, яка стає оптимальною в момент часу $t \geq 0$ t \ge 0, буде унікально оптимальною для будь-якого часу $s$ , що задовольняє $t < s < t + 10$ t < s < t+10. Початкова оптимальна система зв'язку буде унікальною.

Вхідні дані

Кожен тестовий випадок починається з рядка, що містить ціле число $n$ ( $2 \leq n \leq 50$ 2 \le n \le 50), яке вказує на кількість баз астероїдів. Далі йдуть $n$ рядків, кожен з яких містить шість цілих чисел $x$ , $y$ , $z$ , $v_{x}$ v_x, $v_{y}$ v_y, $v_{z}$ v_z. Перші три вказують початкове розташування астероїда ( $- 150 \leq x, y, z \leq 150$ -150 \le x, y, z \le 150), а останні три вказують компоненти швидкості астероїда по осях $x$ , $y$ і $z$ в одиницях простору за одиницю часу ( $- 100 \leq v_{x}, v_{y}, v_{z} \leq 100$ -100 \le v_x, v_y, v_z \le 100).

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить номер випадку та кількість разів, коли систему зв'язку потрібно налаштувати або змінити.

Приклади

Приклад 1