Рассмотрим произвольный набор костей домино, каждая из которых обозначена двумя числами от 1 до 6. Некоторые наборы можно целиком выложить в цепь, в которой числа на стыке соседних костей совпадают, в то время как другие наборы – нельзя. Например, набор, состоящий из костей (1, 5), (1, 6), (5, 5) и двух костей (2, 4), не может быть выложен в цепь. Однако, если мы добавим в набор кость (2, 5), то сможем выложить получившийся набор в следующую цепь:

Но нас интересует цепь с наименьшей суммой чисел на костях. В нашем примере вместо кости (2, 5) с суммой 7 мы могли бы добавить две кости (1, 2) с общей суммой 6 и затем выложить следующую цепь:

Напишите программу, которая для данного набора костей домино найдет дополнительный (возможно, пустой) набор костей с наименьшей возможной суммой чисел, такой, что объединение двух наборов можно выложить в цепь.

В первой строке записано целое число N – общее количество костей в наборе домино (2 ≤ N ≤ 100). Следующие N строк описывают кости. Каждая кость представлена отдельной строкой в виде двух чисел от 1 до 6, разделенных пробелом. Числа могут быть написаны в любом порядке.

В первой строке выведите наименьшую сумму чисел на костях дополнительного набора или 0, если это пустой набор. Во второй строке выведите количество костей в дополнительном наборе или 0, если это пустой набор. Затем перечислите кости дополнительного набора в том же формате, что во входных данных.

Если существует несколько различных дополнительных наборов с одинаковой наименьшей суммой чисел, то выведите любой из них.