#!/usr/bin/python
import sys

def greedify(n,fibbs):
    rev = fibbs[:]
    rev.reverse()
    path = []
    used = [n]
    last = n
    while len(path) < n-1:
        success = False
        for f in rev:
            if f - last > 0 and (f - last) <= n and (f - last) not in used:
                success = True
                path.append((last,f-last))
                used.append(f-last)
                last = f-last
                break
        if not success:
            return []
    #print "PATH: %s" % path
    return path

def makefibbs(n, f, initial):
    #make all "fibonacci" numbers <= n, and make sure
    #we've made all possible f-sums of those numbers
    ret = initial[:]
    while ret[-1] < n:
        ret.append(f(ret[-1], ret[-2]))
    bound = max(f(ret[-1], ret[-2]), f(ret[-2], ret[-1]))
    while ret[-1] < bound:
        ret.append(f(ret[-1], ret[-2]))
    return ret

def general(n, f, initial):
    fibbs = makefibbs(n, f, initial)
    path = greedify(n,fibbs)

    for h in fibbs:
        if h < n:
            second_biggest_fib = h
    print "graph G {"
    for k in range(1,n+1):
        if k in fibbs:
            color = "blue"
        else:
            color = "black"
        if k > second_biggest_fib:
            color = "green"

        
        print "v%d [color=%s,label=\"%s\",shape=circle];" % (k,color,k)
        for j in range(1,k):
            if f(j,k) in fibbs or f(k,j) in fibbs:
                if (k,j) in path or (j,k) in path:
                    color = "red"
                else:
                    color = "black"
                print "v%d -- v%d [color=%s];" % (j,k,color)
    print "};"

def main(n):
    general(n, lambda a,b: a + b, [1,1])

if __name__ == '__main__':
    if len(sys.argv) < 2:
        sys.stderr.write("usage: %s n" % sys.argv[0])
        sys.exit(2)
    else:
        main(int(sys.argv[1]))