Студент Владислав пришёл на экзамен по программированию, совершенно не подготовившись, и, как назло, ему достался билет про какой-то непонятный алгоритм на графе, который абсолютно точно никогда не пригодится ему в жизни. Недолго думая, он попросил у сидящей рядом студентки шпаргалку по этому билету и обнаружил в ней следующий псевдокод алгоритма:
функция пвг(в)
начало
посещено[в] := истина
печатай("in " + в)
для к := 1 : н делай
начало
если являются_соседями(в, к) и не посещено[к] делай
начало
пвг(к)
конец
конец
печатай("out " + в)
конец
Владислав вручную выполнил его на придуманном им самим связном неориентированном графе и получил некоторый результат. К сожалению, от волнения он съел бумажку, на которой был нарисован этот граф, а ведь он должен показать его преподавателю. Помогите Владиславу восстановить граф. Это нужно сделать как можно быстрее, поэтому в полученном графе должно быть минимально возможное количество рёбер.
В первой строке содержится единственное целое число n (1 ≤ n ≤ 105) — количество вершин в графе.
Далее следует результат работы алгоритма, который никогда в жизни не пригодится Владиславу, — 2n строк вида «in x» или «out x», где x — номер вершины (1 ≤ x ≤ n).
Гарантируется, что все вершины от 1 до n присутствуют в графе, и что входные данные действительно задают результат работы алгоритма на некотором реально существующем графе.
Выведите (n - 1) строку, в каждой по 2 целых числа — номера вершин, соединённых очередным ребром. Выводить вершины в паре и пары вершин можно в любом порядке.
2
in 1
in 2
out 2
out 1
1 2
4
in 4
in 2
out 2
in 3
in 1
out 1
out 3
out 4
1 3
2 4
3 4
