Хексадесимал очень любит рисовать. Её перу принадлежит большая коллекция графов, как ориентированных, так и не очень. Недавно она начала работу над натюрмортом «интересный граф и яблоки». Интересным считается такой неориентированный граф, у которого каждая вершина принадлежит только одному циклу: забавному кольцу, и, причём, не принадлежит никакому другому циклу. Забавное кольцо — это такой цикл, который проходит через все вершины графа ровно один раз. Также, к забавным циклам относятся петли.

Яблоки она уже нарисовала и некоторые рёбра в графе тоже. Но теперь стало непонятно, как же соединить оставшиеся вершины, чтобы получился в результате интересный граф? Ответ должен содержать наименьшее количество добавляемых рёбер. И, помимо всего прочего, ответ должен быть лексикографически наименьшим. Набор ребер (x₁, y₁), (x₂, y₂), ..., (x_n, y_n), где x_i ≤ y_i, лексикографически меньше набора (u₁, v₁), (u₂, v₂), ..., (u_n, v_n), где u_i ≤ v_i, в том случае, если последовательность целых чисел x₁, y₁, x₂, y₂, ..., x_n, y_n лексикографически меньше последовательности u₁, v₁, u₂, v₂, ..., u_n, v_n. Если Вы не справитесь, Хексадесимал Вас съест. Живьём.