В конкурсе на лучший проект цветника приняло участие N человек. Каждый из них предоставил свой проект — конечную последовательность точек на плоскости, в которых планируется посадить по цветку. Чтобы избежать ненужной работы основной комисcии по рассмотрению одинаковых проектов, предварительная комиcсия хочет найти проекты, которые отличаются друг от друга перестановкой точек и их аффинным преобразованием, не меняющим ориентацию (радиус-вектор каждой точки умножается на матрицу с положительным определителем и складывается с некоторым фиксированным вектором).
Исходные данные
В первой строке записано число участников N (N ≤ 10000). Далее следует N описаний проектов. Каждое описание проекта начинается с длины последовательности M. Далее на следующих M строчках записаны координаты точек последовательности — пары целых чисел, не превосходящих по модулю 1000. Сумма длин всех последовательностей не превосходит 200000.
Результат
В первой строке вывести количество классов эквивалентности проектов. В следующих строчках вывести сами классы эквивалентности: последовательность номеров проектов (нумерация начинается с 1), в конце последовательности вывести 0.
Пример
исходные данные | результат |
---|
7
5
1 2
0 0
6 0
0 4
2 7
5
1 2
3 9
0 1
2 3
9 2
5
-43 -37
-73 -47
-3 3
-23 -7
-3 63
3
0 0
1 0
0 1
3
0 0
1 0
3 0
3
10 3
3 7
5 2
3
6 1
6 5
6 7 | 4
4 6 0
5 7 0
1 3 0
2 0 |
Автор задачи: Андрей Румянцев
Источник задачи: Petrozavodsk summer training camp, August 2005.