Вернувшись домой с очередной экспедиции на Марс, Вася привёз с собой найденный там чемодан с непонятными каменными прямоугольничками. Каждый из них имел длину в два раза большую, чем ширина и был поделён чертой на 2 квадрата. В каждом квадрате нарисован какой-то значок. И ещё 1 значок нарисован на обратной стороне.
Вася долго бился над разгадкой тайны прямоугольничков. Однажды он проснулся посреди ночи от того, что наконец решил эту задачку. Оказывается, значки сверху - это цифры от 1 до n, а прямоугольнички - это фишки домино. Значок снизу - цена доминошки.
Теперь Васю мучает вопрос: можно ли составить цепочку по правилам игры в домино из всех этих фишек? К тому же он хочет спать, поэтому сам не справится. Помогите Васе решить эту задачу.
Первая строка входного файла содержит натуральное число n - максимальное число, написанное на верхней поверхности фишки (1 ≤ n ≤ 1000). Далее следуют n строк, описывающих доминошки. В i-й из этих строк находится число m_i - количество доминошек, содержащих число i. Далее следует m_i пар положительных чисел: первое - число, написанное на второй половине доминошки, а второе число - её цена.
Может быть несколько одинаковых доминошек, но нет ни одной, на которой с обеих концов написано одно и то же число.
Все числа во входном файле не превосходят 10^5; гарантируется, что общее число доминошек не меньше единицы и не превосходит 10^5.
Если решение существует, то в первую строку выходного файла выведите одно число - количество доминошек в искомой цепочке (считая первую и последнюю), а во вторую - числа, в порядке, в котором они будут лежать в цепи (место соединения доминошек выводить как одно число - см. пример).
Если решений нет, выведите в выходной файл одно число -1.
Если решений несколько, выведите любое.