ACM PKU 1944

В начале положим ans=N (все ребра присутствуют). Теперь переберем ребро, которое не присутствует (т.е. место где размыкается цикл). Теперь для каждой пары однозначно определено направление по которому мы будем соединять ребра внутри круга, поэтому просто проходим по всем вершинам и если какое-то ребро начинается в данной вершине, прибавляем к счетчику 1, а если заканчивается - отнимаем 1. Если счетчик не 0, то ставим очередное ребро, иначе не ставим. Ну и каждый раз пытаемся улучшить ans. Сложность выходит O(N^2).