#!/usr/bin/env python

# Emulate a breadth-first traversal of the "flip"
# of the tree defined by the Hofstadter H-sequence.
def hflip_iter():
    yield 0
    yield 1
    # Start on the first node of a left branch, parent node is 1.
    queue = [(1, 1)]
    n = 2
    while True:
        parent, state = queue.pop(0)
        yield parent
        if state == 0:
            # Root node. Add the two children.
            queue.append((n, 1))
            queue.append((n, 0))
        elif state == 1:
            # First node on left branch. Add the second node.
            queue.append((n, 2))
        elif state == 2:
            # Second node on left branch. Add a new root.
            queue.append((n, 0))
        n += 1

i = hflip_iter()
for n in range(0, 10001):
    print n, i.next()