class Graph:
def init(self):
self.V = []

class Vertex:
def init(self, x):
self.key = x
self.color = 'white'
self.d = 10000
self.f = 10000
self.pi = None
self.adj = []
self.next = None

class Solution:
def Dfs(self, G):
for u in G.V:
u.color = 'white'
u.pi = None
global time
time = 0
for u in G.V:
if u.color == 'white':
self.DfsVisit(G, u)

def DfsVisit(self, G, u):
    global time
    time = time + 1
    u.d = time
    u.color = 'gray'
    for v in u.adj:
        if v.color == 'white':
            self.DfsVisit(G, v)
            v.pi = u
    u.color = 'black'
    time = time + 1
    u.f = time

def TopologicalSort(self, G):
    LinkedList = Vertex('#')
    self.Dfs(G)
    G.V.sort(key=lambda v:v.f)
    for v in G.V:
        v.next = LinkedList.next
        LinkedList.next = v
    return LinkedList

if name == 'main':
undershorts = Vertex('undershorts')
socks = Vertex('socks')
pants = Vertex('pants')
shoes = Vertex('shoes')
belt = Vertex('belt')
shirt = Vertex('shirt')
tie = Vertex('tie')
jacket = Vertex('jacket')
watch = Vertex('watch')

undershorts.adj = [pants, shoes]
socks.adj = [shoes]
pants.adj = [belt, shoes]
shoes.adj = []
belt.adj = [jacket]
shirt.adj = [belt, tie]
tie.adj = [jacket]
jacket.adj = []
watch.adj = []

G = Graph()
G.V = [undershorts,socks,pants,shoes,belt,shirt,tie,jacket,watch]

m = Solution()
Sort_List = m.TopologicalSort(G)
p = Sort_List
while p.next != None:
    print(p.next.key, p.next.f)
    p = p.next