402197: GYM100694 G The Lost Graph

Student Vladislav is taking programming exam. He hasn't prepared properly and had a bad luck to get a question about some complicated graph algorithm that will be definitely useless for him for the rest of his life. He quickly asked his groupmate a cheatsheet and discovered the following pseudocode there:

function dfs(v)
begin
    visited[v] := true
    print("in " + v)
    for k := 1 : n do
    begin
        if adjacent(v, k) and not visited[k] do
        begin
            dfs(k)
        end
    end
    print("out " + v)
end

Vladislav manually executed the algorithm on the connected undirected graph just drawn by him. Unfortunately, he was very nervous and ate the piece of paper where this graph was drawn, but he has to show the graph to his teacher. Help Vladislav to restore the graph. It must be done as soon as possible, so the restored graph should contain the minimal possible number of edges.

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of vertices in the graph.

It's followed by the execution result of the algorithm completely useless for Vladislav. It consists of 2n lines «in x» or «out x» where x is the number of vertex (1 ≤ x ≤ n).

It's guaranteed that all vertices from 1 to n exist in the graph, and that the input really specifies the execution result of the algorithm on some existing graph.

Output (n - 1) lines, two numbers on each line — the numbers of vertices connected by edges. You can output the pairs of vertices and the vertices in pairs in any order.

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