#!/usr/bin/python3
from pygraph import *
from pygraph.readwrite import markup
from sys import argv
gr = markup.read(open(argv[1]).read())

def depth(root, n):
  if root + "_depth" in gr.node_attributes(n):
    return 0
  gr.add_node_attribute(n,root + "_depth")
  d = 0
  for n2 in gr.neighbors(n):
    subdepth = depth(root, n2)
    if subdepth + 1 > d:
      d = subdepth + 1
  return d

def patriarchy(root, n):
  if root + "_patriarchy" in gr.node_attributes(n):
    return (1, [n])
  gr.add_node_attribute(n, root + "_patriarchy")
  p = 1
  maxpat = 0
  subpath = [ ]
  for n2 in gr.neighbors(n):
    pat, spath = patriarchy(root, n2)
    if pat > maxpat:
      maxpat = pat
      subpath = spath
    p += pat
  return p, ([ n ] + subpath)

def path(root, n):
  if root + "_path" in gr.node_attributes(n):
    return (0, [n])
  gr.add_node_attribute(n, root + "_path")
  d = 0
  p = [ n ]
  for n2 in gr.neighbors(n):
    (subdepth, subpath) = path(root, n2)
    if subdepth + 1 > d:
      d = subdepth + 1
      p = [ n ] + subpath
  return (d, p)

for i in gr.nodes():
  if (u'red', '') in gr.node_attributes(i) \
  or (u'black', '') in gr.node_attributes(i) \
  or (u'yellow', '') in gr.node_attributes(i) \
  or (u'magenta', '') in gr.node_attributes(i) \
  or (u'cyan', '') in gr.node_attributes(i) \
  or (u'orange', '') in gr.node_attributes(i) \
  or (u'purple', '') in gr.node_attributes(i) \
    :
    pat,path = patriarchy(i, i)
    print(pat, "	", depth(i, i), "	", i, "		", path)