from collections import deque
import random
 
 
def is_topsorted(V,E,sequence):
  sequence = list(sequence)
  #from wikipedia definition of top-sort
  #for every edge uv, u comes before v in the ordering
  for u,v in E:
    ui = sequence.index(u)
    vi = sequence.index(v)
    if not (ui < vi):
      return False
  return True 
 
#the collection_type should behave like a set:
# it must have add(), pop() and __len__() as members.
def topsort(V,E,collection_type):
  #out edges
  INS = {}
 
  #in edges
  OUTS = {}
  for v in V:
    INS[v] = set()
    OUTS[v] = set()
 
  #for each edge u,v,
  for u,v in E:
    #record the out-edge from u
    OUTS[u].add(v)
    #record the in-edge to v
    INS[v].add(u)
 
  #1. Store all vertices with indegree 0 in a queue
  #We will start
  topvertices = collection_type()
 
  for v,in_vertices in INS.iteritems():
    if len(in_vertices) == 0:
      topvertices.add(v)
 
  result = []
 
  #4. Perform steps 2 and 3 while the queue is not empty.
  while len(topvertices) != 0:  
    #2. get a vertex U and place it in the sorted sequence (array or another queue).
    u = topvertices.pop()
    result.append(u)
 
    #3. For all edges (U,V) update the indegree of V,
    # and put V in the queue if the updated indegree is 0.
 
    for v in OUTS[u]:
      INS[v].remove(u)
      if len(INS[v]) == 0:
        topvertices.add(v)
 
  return result
 
class stack_collection:
  def __init__(self):
    self.data = list()
  def add(self,v):
    self.data.append(v)
  def pop(self):
    return self.data.pop()
  def __len__(self):
    return len(self.data)
 
class queue_collection:
  def __init__(self):
    self.data = deque()
  def add(self,v):
    self.data.append(v)
  def pop(self):
    return self.data.popleft()
  def __len__(self):
    return len(self.data)
 
class random_orderd_collection:
  def __init__(self):
    self.data = []
  def add(self,v):
    self.data.append(v)
  def pop(self):    
    result = random.choice(self.data)
    self.data.remove(result)
    return result
  def __len__(self):
    return len(self.data)
 
"""
Poor man's graph generator.
Requires networkx.
 
Don't make the edge_count too high compared with the vertex count,
 otherwise it will run for a long time or forever.
"""
def nx_generate_random_dag(vertex_count,edge_count):
  import networkx as nx
 
  V = range(1,vertex_count+1)
  random.shuffle(V)
 
  G = nx.DiGraph()
  G.add_nodes_from(V)
 
  while nx.number_of_edges(G) < edge_count:
 
    u = random.choice(V)
    v = random.choice(V)
    if u == v:
      continue
 
    for tries in range(2):
      G.add_edge(u,v)
      if not nx.is_directed_acyclic_graph(G):
        G.remove_edge(u,v)
        u,v = v,u
  V = G.nodes()
  E = G.edges()
 
  assert len(E) == edge_count
  assert len(V) == vertex_count
  return V,E
 
 
 
 
def main():
 
  graphs = []
 
  V = [1,2,3,4,5]
  E = [(1,2),(1,5),(1,4),(2,4),(2,5),(3,4),(3,5)]
 
  graphs.append((V,E))
 
  """
  Uncomment this section if you have networkx.
  This will generate 3 random graphs.
  """
  """
  for i in range(3):
    G = nx_generate_random_dag(30,120)
    V,E = G
    print 'random E:',E
    graphs.append(G)
  """
 
 
  #This graph was generated using nx_generate_random_dag() from above
  V = range(1,31)
  E = [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23),
       (1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19),
       (2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26),
       (5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29),
       (7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12),
       (9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28),
       (9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5),
       (12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24),
       (14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19),
       (15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23),
       (16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28),
       (18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29),
       (21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10),
       (24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3),
       (26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4),
       (29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7),
       (30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)]
 
  graphs.append((V,E))
 
  #add other graphs here for testing
 
 
  for G in graphs:
    V,E = G
 
    #sets in python are unordered but in practice their hashes usually order integers.
    top_set = topsort(V,E,set)
 
    top_stack = topsort(V,E,stack_collection)
 
    top_queue = topsort(V,E,queue_collection)
 
    random_results = []
    for i in range(0,10):
      random_results.append(topsort(V,E,random_orderd_collection))
 
    print
    print 'V: ', V
    print 'E: ', E
    print 'top_set ({0}): {1}'.format(is_topsorted(V,E,top_set),top_set)
    print 'top_stack ({0}): {1}'.format(is_topsorted(V,E,top_stack),top_stack)
    print 'top_queue ({0}): {1}'.format(is_topsorted(V,E,top_queue),top_queue)
 
    for random_result in random_results:
      print 'random_result ({0}): {1}'.format(is_topsorted(V,E,random_result),random_result)
      assert is_topsorted(V,E,random_result)
 
    assert is_topsorted(V,E,top_set)
    assert is_topsorted(V,E,top_stack)
    assert is_topsorted(V,E,top_queue)
 
 
 
main()
 
 
 

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKaW1wb3J0IHJhbmRvbQoKCmRlZiBpc190b3Bzb3J0ZWQoVixFLHNlcXVlbmNlKToKICBzZXF1ZW5jZSA9IGxpc3Qoc2VxdWVuY2UpCiAgI2Zyb20gd2lraXBlZGlhIGRlZmluaXRpb24gb2YgdG9wLXNvcnQKICAjZm9yIGV2ZXJ5IGVkZ2UgdXYsIHUgY29tZXMgYmVmb3JlIHYgaW4gdGhlIG9yZGVyaW5nCiAgZm9yIHUsdiBpbiBFOgogICAgdWkgPSBzZXF1ZW5jZS5pbmRleCh1KQogICAgdmkgPSBzZXF1ZW5jZS5pbmRleCh2KQogICAgaWYgbm90ICh1aSA8IHZpKToKICAgICAgcmV0dXJuIEZhbHNlCiAgcmV0dXJuIFRydWUgCgojdGhlIGNvbGxlY3Rpb25fdHlwZSBzaG91bGQgYmVoYXZlIGxpa2UgYSBzZXQ6CiMgaXQgbXVzdCBoYXZlIGFkZCgpLCBwb3AoKSBhbmQgX19sZW5fXygpIGFzIG1lbWJlcnMuCmRlZiB0b3Bzb3J0KFYsRSxjb2xsZWN0aW9uX3R5cGUpOgogICNvdXQgZWRnZXMKICBJTlMgPSB7fQogIAogICNpbiBlZGdlcwogIE9VVFMgPSB7fQogIGZvciB2IGluIFY6CiAgICBJTlNbdl0gPSBzZXQoKQogICAgT1VUU1t2XSA9IHNldCgpCgogICNmb3IgZWFjaCBlZGdlIHUsdiwKICBmb3IgdSx2IGluIEU6CiAgICAjcmVjb3JkIHRoZSBvdXQtZWRnZSBmcm9tIHUKICAgIE9VVFNbdV0uYWRkKHYpCiAgICAjcmVjb3JkIHRoZSBpbi1lZGdlIHRvIHYKICAgIElOU1t2XS5hZGQodSkKICAKICAjMS4gU3RvcmUgYWxsIHZlcnRpY2VzIHdpdGggaW5kZWdyZWUgMCBpbiBhIHF1ZXVlCiAgI1dlIHdpbGwgc3RhcnQKICB0b3B2ZXJ0aWNlcyA9IGNvbGxlY3Rpb25fdHlwZSgpCgogIGZvciB2LGluX3ZlcnRpY2VzIGluIElOUy5pdGVyaXRlbXMoKToKICAgIGlmIGxlbihpbl92ZXJ0aWNlcykgPT0gMDoKICAgICAgdG9wdmVydGljZXMuYWRkKHYpCgogIHJlc3VsdCA9IFtdCgogICM0LiBQZXJmb3JtIHN0ZXBzIDIgYW5kIDMgd2hpbGUgdGhlIHF1ZXVlIGlzIG5vdCBlbXB0eS4KICB3aGlsZSBsZW4odG9wdmVydGljZXMpICE9IDA6ICAKICAgICMyLiBnZXQgYSB2ZXJ0ZXggVSBhbmQgcGxhY2UgaXQgaW4gdGhlIHNvcnRlZCBzZXF1ZW5jZSAoYXJyYXkgb3IgYW5vdGhlciBxdWV1ZSkuCiAgICB1ID0gdG9wdmVydGljZXMucG9wKCkKICAgIHJlc3VsdC5hcHBlbmQodSkKCiAgICAjMy4gRm9yIGFsbCBlZGdlcyAoVSxWKSB1cGRhdGUgdGhlIGluZGVncmVlIG9mIFYsCiAgICAjIGFuZCBwdXQgViBpbiB0aGUgcXVldWUgaWYgdGhlIHVwZGF0ZWQgaW5kZWdyZWUgaXMgMC4KCiAgICBmb3IgdiBpbiBPVVRTW3VdOgogICAgICBJTlNbdl0ucmVtb3ZlKHUpCiAgICAgIGlmIGxlbihJTlNbdl0pID09IDA6CiAgICAgICAgdG9wdmVydGljZXMuYWRkKHYpCgogIHJldHVybiByZXN1bHQKCmNsYXNzIHN0YWNrX2NvbGxlY3Rpb246CiAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgc2VsZi5kYXRhID0gbGlzdCgpCiAgZGVmIGFkZChzZWxmLHYpOgogICAgc2VsZi5kYXRhLmFwcGVuZCh2KQogIGRlZiBwb3Aoc2VsZik6CiAgICByZXR1cm4gc2VsZi5kYXRhLnBvcCgpCiAgZGVmIF9fbGVuX18oc2VsZik6CiAgICByZXR1cm4gbGVuKHNlbGYuZGF0YSkKCmNsYXNzIHF1ZXVlX2NvbGxlY3Rpb246CiAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgc2VsZi5kYXRhID0gZGVxdWUoKQogIGRlZiBhZGQoc2VsZix2KToKICAgIHNlbGYuZGF0YS5hcHBlbmQodikKICBkZWYgcG9wKHNlbGYpOgogICAgcmV0dXJuIHNlbGYuZGF0YS5wb3BsZWZ0KCkKICBkZWYgX19sZW5fXyhzZWxmKToKICAgIHJldHVybiBsZW4oc2VsZi5kYXRhKQoKY2xhc3MgcmFuZG9tX29yZGVyZF9jb2xsZWN0aW9uOgogIGRlZiBfX2luaXRfXyhzZWxmKToKICAgIHNlbGYuZGF0YSA9IFtdCiAgZGVmIGFkZChzZWxmLHYpOgogICAgc2VsZi5kYXRhLmFwcGVuZCh2KQogIGRlZiBwb3Aoc2VsZik6ICAgIAogICAgcmVzdWx0ID0gcmFuZG9tLmNob2ljZShzZWxmLmRhdGEpCiAgICBzZWxmLmRhdGEucmVtb3ZlKHJlc3VsdCkKICAgIHJldHVybiByZXN1bHQKICBkZWYgX19sZW5fXyhzZWxmKToKICAgIHJldHVybiBsZW4oc2VsZi5kYXRhKQoKIiIiClBvb3IgbWFuJ3MgZ3JhcGggZ2VuZXJhdG9yLgpSZXF1aXJlcyBuZXR3b3JreC4KCkRvbid0IG1ha2UgdGhlIGVkZ2VfY291bnQgdG9vIGhpZ2ggY29tcGFyZWQgd2l0aCB0aGUgdmVydGV4IGNvdW50LAogb3RoZXJ3aXNlIGl0IHdpbGwgcnVuIGZvciBhIGxvbmcgdGltZSBvciBmb3JldmVyLgoiIiIKZGVmIG54X2dlbmVyYXRlX3JhbmRvbV9kYWcodmVydGV4X2NvdW50LGVkZ2VfY291bnQpOgogIGltcG9ydCBuZXR3b3JreCBhcyBueAogIAogIFYgPSByYW5nZSgxLHZlcnRleF9jb3VudCsxKQogIHJhbmRvbS5zaHVmZmxlKFYpCiAgCiAgRyA9IG54LkRpR3JhcGgoKQogIEcuYWRkX25vZGVzX2Zyb20oVikKCiAgd2hpbGUgbngubnVtYmVyX29mX2VkZ2VzKEcpIDwgZWRnZV9jb3VudDoKCiAgICB1ID0gcmFuZG9tLmNob2ljZShWKQogICAgdiA9IHJhbmRvbS5jaG9pY2UoVikKICAgIGlmIHUgPT0gdjoKICAgICAgY29udGludWUKICAgIAogICAgZm9yIHRyaWVzIGluIHJhbmdlKDIpOgogICAgICBHLmFkZF9lZGdlKHUsdikKICAgICAgaWYgbm90IG54LmlzX2RpcmVjdGVkX2FjeWNsaWNfZ3JhcGgoRyk6CiAgICAgICAgRy5yZW1vdmVfZWRnZSh1LHYpCiAgICAgICAgdSx2ID0gdix1CiAgViA9IEcubm9kZXMoKQogIEUgPSBHLmVkZ2VzKCkKICAKICBhc3NlcnQgbGVuKEUpID09IGVkZ2VfY291bnQKICBhc3NlcnQgbGVuKFYpID09IHZlcnRleF9jb3VudAogIHJldHVybiBWLEUKICAKICAKCiAgCmRlZiBtYWluKCk6CgogIGdyYXBocyA9IFtdCgogIFYgPSBbMSwyLDMsNCw1XQogIEUgPSBbKDEsMiksKDEsNSksKDEsNCksKDIsNCksKDIsNSksKDMsNCksKDMsNSldCgogIGdyYXBocy5hcHBlbmQoKFYsRSkpCgogICIiIgogIFVuY29tbWVudCB0aGlzIHNlY3Rpb24gaWYgeW91IGhhdmUgbmV0d29ya3guCiAgVGhpcyB3aWxsIGdlbmVyYXRlIDMgcmFuZG9tIGdyYXBocy4KICAiIiIKICAiIiIKICBmb3IgaSBpbiByYW5nZSgzKToKICAgIEcgPSBueF9nZW5lcmF0ZV9yYW5kb21fZGFnKDMwLDEyMCkKICAgIFYsRSA9IEcKICAgIHByaW50ICdyYW5kb20gRTonLEUKICAgIGdyYXBocy5hcHBlbmQoRykKICAiIiIKCiAgCiAgI1RoaXMgZ3JhcGggd2FzIGdlbmVyYXRlZCB1c2luZyBueF9nZW5lcmF0ZV9yYW5kb21fZGFnKCkgZnJvbSBhYm92ZQogIFYgPSByYW5nZSgxLDMxKQogIEUgPSBbKDEsIDEwKSwgKDEsIDExKSwgKDEsIDE0KSwgKDEsIDE3KSwgKDEsIDE4KSwgKDEsIDIxKSwgKDEsIDIzKSwKICAgICAgICgxLCAzMCksICgyLCA0KSwgKDIsIDEyKSwgKDIsIDE1KSwgKDIsIDE3KSwgKDIsIDE4KSwgKDIsIDE5KSwKICAgICAgICgyLCAyNSksICgzLCAyMiksICg0LCA1KSwgKDQsIDgpLCAoNCwgMjIpLCAoNCwgMjMpLCAoNCwgMjYpLAogICAgICAgKDUsIDI3KSwgKDUsIDIzKSwgKDYsIDI0KSwgKDYsIDI4KSwgKDYsIDI3KSwgKDYsIDIwKSwgKDYsIDI5KSwKICAgICAgICg3LCAzKSwgKDcsIDE5KSwgKDcsIDEzKSwgKDgsIDI0KSwgKDgsIDEwKSwgKDgsIDMpLCAoOCwgMTIpLAogICAgICAgKDksIDQpLCAoOSwgOCksICg5LCAxMCksICg5LCAxNCksICg5LCAxOSksICg5LCAyNyksICg5LCAyOCksCiAgICAgICAoOSwgMjkpLCAoMTAsIDE4KSwgKDEwLCA1KSwgKDEwLCAyMyksICgxMSwgMjcpLCAoMTEsIDUpLAogICAgICAgKDEyLCAxMCksICgxMywgOSksICgxMywgMjYpLCAoMTMsIDMpLCAoMTMsIDEyKSwgKDEzLCA2KSwgKDE0LCAyNCksCiAgICAgICAoMTQsIDI4KSwgKDE0LCAxOCksICgxNCwgMjApLCAoMTUsIDMpLCAoMTUsIDEyKSwgKDE1LCAxNyksICgxNSwgMTkpLAogICAgICAgKDE1LCAyNSksICgxNSwgMjcpLCAoMTYsIDQpLCAoMTYsIDUpLCAoMTYsIDgpLCAoMTYsIDE4KSwgKDE2LCAyMCksICgxNiwgMjMpLAogICAgICAgKDE2LCAyNiksICgxNiwgMjgpLCAoMTcsIDQpLCAoMTcsIDUpLCAoMTcsIDgpLCAoMTcsIDEyKSwgKDE3LCAyMiksICgxNywgMjgpLAogICAgICAgKDE4LCAxMSksICgxOCwgMyksICgxOSwgMTApLCAoMTksIDE4KSwgKDE5LCA1KSwgKDE5LCAyMiksICgyMCwgNSksICgyMCwgMjkpLAogICAgICAgKDIxLCAyNSksICgyMSwgMTIpLCAoMjEsIDMwKSwgKDIxLCAxNyksICgyMiwgMTEpLCAoMjQsIDMpLCAoMjQsIDEwKSwKICAgICAgICgyNCwgMTEpLCAoMjQsIDI4KSwgKDI1LCAxMCksICgyNSwgMTcpLCAoMjUsIDIzKSwgKDI1LCAyNyksICgyNiwgMyksCiAgICAgICAoMjYsIDE4KSwgKDI2LCAxOSksICgyOCwgMjYpLCAoMjgsIDExKSwgKDI4LCAyMyksICgyOSwgMiksICgyOSwgNCksCiAgICAgICAoMjksIDExKSwgKDI5LCAxNSksICgyOSwgMTcpLCAoMjksIDIyKSwgKDI5LCAyMyksICgzMCwgMyksICgzMCwgNyksCiAgICAgICAoMzAsIDE3KSwgKDMwLCAyMCksICgzMCwgMjUpLCAoMzAsIDI2KSwgKDMwLCAyOCksICgzMCwgMjkpXQoKICBncmFwaHMuYXBwZW5kKChWLEUpKQoKICAjYWRkIG90aGVyIGdyYXBocyBoZXJlIGZvciB0ZXN0aW5nCgoKICBmb3IgRyBpbiBncmFwaHM6CiAgICBWLEUgPSBHCgogICAgI3NldHMgaW4gcHl0aG9uIGFyZSB1bm9yZGVyZWQgYnV0IGluIHByYWN0aWNlIHRoZWlyIGhhc2hlcyB1c3VhbGx5IG9yZGVyIGludGVnZXJzLgogICAgdG9wX3NldCA9IHRvcHNvcnQoVixFLHNldCkKCiAgICB0b3Bfc3RhY2sgPSB0b3Bzb3J0KFYsRSxzdGFja19jb2xsZWN0aW9uKQoKICAgIHRvcF9xdWV1ZSA9IHRvcHNvcnQoVixFLHF1ZXVlX2NvbGxlY3Rpb24pCgogICAgcmFuZG9tX3Jlc3VsdHMgPSBbXQogICAgZm9yIGkgaW4gcmFuZ2UoMCwxMCk6CiAgICAgIHJhbmRvbV9yZXN1bHRzLmFwcGVuZCh0b3Bzb3J0KFYsRSxyYW5kb21fb3JkZXJkX2NvbGxlY3Rpb24pKQogICAgCiAgICBwcmludAogICAgcHJpbnQgJ1Y6ICcsIFYKICAgIHByaW50ICdFOiAnLCBFCiAgICBwcmludCAndG9wX3NldCAoezB9KTogezF9Jy5mb3JtYXQoaXNfdG9wc29ydGVkKFYsRSx0b3Bfc2V0KSx0b3Bfc2V0KQogICAgcHJpbnQgJ3RvcF9zdGFjayAoezB9KTogezF9Jy5mb3JtYXQoaXNfdG9wc29ydGVkKFYsRSx0b3Bfc3RhY2spLHRvcF9zdGFjaykKICAgIHByaW50ICd0b3BfcXVldWUgKHswfSk6IHsxfScuZm9ybWF0KGlzX3RvcHNvcnRlZChWLEUsdG9wX3F1ZXVlKSx0b3BfcXVldWUpCgogICAgZm9yIHJhbmRvbV9yZXN1bHQgaW4gcmFuZG9tX3Jlc3VsdHM6CiAgICAgIHByaW50ICdyYW5kb21fcmVzdWx0ICh7MH0pOiB7MX0nLmZvcm1hdChpc190b3Bzb3J0ZWQoVixFLHJhbmRvbV9yZXN1bHQpLHJhbmRvbV9yZXN1bHQpCiAgICAgIGFzc2VydCBpc190b3Bzb3J0ZWQoVixFLHJhbmRvbV9yZXN1bHQpCgogICAgYXNzZXJ0IGlzX3RvcHNvcnRlZChWLEUsdG9wX3NldCkKICAgIGFzc2VydCBpc190b3Bzb3J0ZWQoVixFLHRvcF9zdGFjaykKICAgIGFzc2VydCBpc190b3Bzb3J0ZWQoVixFLHRvcF9xdWV1ZSkKICAgIAoKCm1haW4oKQoKCg==