import sys

def load_edges(fname):
   f = open(fname,"r");
   edge_list = []
   maxv  = 0
   for line in f:
       n1, n2 = map(int, line.split())
       edge_list.append([ n1, n2 ])
   return edge_list

class Graph:

   def __init__(self, edge_list):

       vlist = []
       self.maxv = 0
       for edge in edge_list:
           self.maxv = max(self.maxv, edge[0], edge[1])

       self.adj = []
       for v in xrange(self.maxv + 1):
           self.adj.append([])

       for edge in edge_list:
           self.adj[edge[0]].append(edge[1])

   def vlist(self):
       return xrange(0, self.maxv + 1)


class SccAlgo:

    def __init__(self, edge_list):
       self.edge_list = edge_list

    def reverse_edges(self):
        rlist = []
        for edge in self.edge_list:
            rlist.append([edge[1], edge[0]])
        return rlist

    def dfs(self, graph, i):
       self.leader[i] = self.s
       self.explored[i] = True
       for j in graph.adj[i]:
           if not self.explored[j]:
               self.dfs(graph, j)
       self.t += 1
       self.finish[i] = self.t


    def dfs_loop(self, graph):
        print "clear"
        self.t = 0
        self.s = 0
        for i in graph.vlist():
            self.explored[i] = False
            self.leader[i] = 0
            self.finish[i] = 0
        print "start exploration"
        for i in xrange(graph.maxv, 0, -1):
            #print "explore "+str(i)
            if not self.explored[i]:
                self.s = i
                self.dfs(graph, i)
        print "end exploration"

    def first_pass(self):
       graph = Graph(self.reverse_edges())
       self.explored = [ False ] * (graph.maxv + 1)
       self.leader = [ 0 ] * (graph.maxv + 1)
       self.finish = [ 0 ] * (graph.maxv + 1)
       self.dfs_loop(graph)

    def second_pass(self):

        renamed = []
        for edge in self.edge_list:
            renamed.append([ self.finish[edge[0]], self.finish[edge[1]]])

        graph = Graph(renamed)
        self.dfs_loop(graph)

    def debug(self):
        for i in range(len(self.explored)):
            print i, self.explored[i], self.leader[i], self.finish[i]

    def stats(self):
        stats = dict()
        for i in range(len(self.leader)):
            key = self.leader[i]
            stats[key] = stats.setdefault(key, 0) + 1
        print stats


sys.setrecursionlimit(32800)
print sys.getrecursionlimit()

algo = SccAlgo(load_edges("SCC.txt"))
print "first pass"
algo.first_pass()
#algo.debug()
#print "second pass"
#algo.second_pass()
#algo.debug()
#algo.stats()