На недавно открытой планете первопроходцы нашли разрушенные поселения двух различных цивилизаций в разных местах. Мы будем считать, что все этим места можно представить как точки на плоскости. Они хотят узнать больше об этих цивилизациях, но для изучения местности им нужно построить дороги между некоторыми поселениями. Но, как всегда, есть некоторые ограничения:
- между любой парой поселений, относящихся к одной и той же цивилизации, должен быть ровно один путь по построенным дорогам;
- никакие два поселения, относящиеся к разным цивилизациям, не должны быть соединены дорогой (первопроходцы не хотят случайно спутать цивилизации, которые изучают);
- каждая дорога должна быть отрезком прямой;
- так как строить перекрестки слишком дорого, то никакие две дороги не должны пересекаться (то есть общие точки у дорог могут быть только в каком-то из поселений).
Конечно, положения всех поселений различны, но у первопроходцев есть для вас еще одна отличная новость: никакие три поселения не лежат на одной прямой!
Помогите первопроходцами и найдите решение их задачи, либо сообщите, что это невозможно.
Выходные данные
В первой строке выведите число дорог, которые необходимо построить.
В следующих строках выведите все пары поселений (нумерация с \(0\)), которые должны быть соединены дорогами.
Если невозможно построить дороги так, чтобы выполнялись все условия, выведите «Impossible» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 0 1
1 0 0
0 1 0
1 1 1
3 2 0
|
3
1 4
4 2
3 0
|