[Герыч]

Да, максимумы. Я просто объясняю форумулу:
каждой вершине присвоим число k, а потом будет брать любые 2 вершины и уменьшать число, приписанное вершине на 1, а число рёбер увеличивать на 1. Как не думай, больше чем k*n/2 раз не получится.