Сузір'я#635

Сузір'я

3 секунди

64 мегабайти

Середня

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

Щоб розпізнавати сузір'я, Вадим вигадав просте правило: зірка $A$ належить до одного сузір'я з усіма зірками, чиї зображення "не надто далеко" від її зображення. Нехай $d$ — це відстань від зображення зірки $A$ до найближчого зображення іншої зірки. Вадим включає у це ж сузір'я ті зірки, чиї зображення знаходяться на відстані не більшій за $k \cdot d$ k \cdot d, де $k$ — це ціле число, яке Вадим обирає заздалегідь.

Він застосовує це правило так. Зірки $A$ та $B$ вважаються такими, що належать одному сузір'ю, якщо існує послідовність зірок $A = u_{1}, u_{2}, \dots, u_{l} = B$ A = u_1, u_2, \ldots, u_l = B така, що для будь-яких двох сусідніх зірок $u_{i}$ u_i та $u_{i + 1}$ u_{i+1} у цій послідовності виконується принаймні одна з двох умов:

Відстань між їх зображеннями не перевищує $k \cdot md (u_{i})$ k \cdot \text{md}(u_i), де $md (X)$ означає відстань від зображення зірки $X$ до найближчого зображення іншої зірки;
Відстань між їх зображеннями не перевищує $k \cdot md (u_{i + 1})$ k \cdot \text{md}(u_{i+1}).

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

Ваше завдання — написати програму, яка, використовуючи інформацію про координати зображень зірок на фотографії, групує зірки у сузір'я за методом Вадима.

Вхідні дані

Перший рядок містить два цілі числа: $n$ — кількість зірок на фотографії ( $2 \leq n \leq 5000$ 2 \leq n \leq 5000) та $k$ ( $1 \leq k \leq 10$ 1 \leq k \leq 10). Кожен з наступних $n$ рядків містить два числа — $x_{i}$ x_i і $y_{i}$ y_i — координати $i$ -тої зірки ( $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{5}$ |x_i|, |y_i| \leq 10^5). Зображення всіх зірок розташовані у різних точках.

Вихідні дані

Виведіть число $m$ — кількість сузір'їв. У наступних $m$ рядках виведіть описи сузір'їв. Кожен опис повинен містити число $n_{i}$ n_i — кількість зірок у цьому сузір'ї, а також $n_{i}$ n_i чисел — номери цих зірок. Зірки пронумеровані від $1$ до $n$ у порядку подання у вхідних даних.

Приклади

Приклад 1