Сергей открыл глаза и понял, что он в игре. Он был на маленьком островке с другими мальчишками и девчонками, сражающимися деревянными мечами и пытающимися захватить соседние острова. Всего было сорок островов в безбрежном океане, и каждый из них был соединен мостами ровно с тремя другими. В игре было всего три основным правила: не играть после развода мостов, не играть в поддавки и не смотреть вверх, когда заходит солнце.
Когда Сергей настолько близок к панике, он пытается думать над математическими задачами. Поэтому ему неважно, что его могут убить в любой момент, кто автор этой книги, какова цель этой глупой игры и как отсюда выбраться. Он сосредоточился на одном единственном вопросе: возможно ли происходящее с геометрической точки зрения? Поскольку Сергей любит обобщения, он пришел к следующей задаче.
Рассмотрим архипелаг, состоящий из n × m островов, расположенных во всех возможных точках с целочисленными координатами (x, y), 0 ≤ x < n, 0 ≤ y < m. Нужно соединить некоторые пары островов мостами (прямолинейными отрезками) таким образом, чтобы:
Входные данные состоят из нескольких тестов. Каждый тест состоит из трех целых чисел n, m и p (1 ≤ n, m ≤ 100, 1 ≤ p ≤ 8), которые задают размеры архипелага и количество соседей для каждого острова, с которыми он должен быть соединен мостами.
Для каждого теста выведите его номер. Затем, если задача не имеет решения, выведите «-1». Иначе выведите одно вещественное число — минимальную суммарную длину мостов. Абсолютная или относительная погрешность не должна превышать 10 - 6. Во второй строке выведите количество мостов. В следующих строках должны содержаться описания мостов, по одному в строке. Каждый мост описывается четверкой чисел «x1 y1 x2 y2» — координатами двух островов, которые он соединяет. Порядок мостов и порядок точек в каждой паре не имеют значения. Если решений несколько, выведите любое.
2 2 2
2 2 3
Case 1: 4.0000000000
4
1 1 1 0
1 1 0 1
1 0 0 0
0 1 0 0
Case 2: -1
