kingdom_connectivity.py

class Paths(object):
    def __init__(self, E, N):
        self.N = N
        self.E = E
        self.start = 0
        self.end = N-1
        self.count = 0
        self.colors = [0 for x in xrange(N)]
        self.cycles = [0 for x in xrange(N)]
        self.values = [0 for x in xrange(N)]
        
    def neighbours(self, v):
        return self.E[v]
    
    def find(self, node):
        if self.colors[node] == 0:  # pierwszy raz
            self.colors[node] = 1
        
        if node == self.end:
            self.values[node] = 1
        else:
            self.values[node] = 0
            for n in self.neighbours(node):
                if self.colors[n] == 1:  # drugi raz bylibyśmy w sąsiedzie
                    self.cycles[n] = 1
                elif self.colors[n] == 2:
                    self.values[node] += self.values[n] % 10**9
                else:
                    self.values[node] += self.find(n) % 10**9
                    
        self.colors[node] = 2
        return self.values[node] % 10**9
    
    def run(self):
        self.count = self.find(self.start)
        

        

N, M = map(int, raw_input().split())
E = {x:[] for x in xrange(N)}
for i in xrange(M):
    x, y =  map(int, raw_input().split())
    E[x-1].append(y-1)
    
    
paths = Paths(E, N)
paths.run()
infinite = False
for x in xrange(N):
    if paths.values[x] and paths.cycles[x]:
        infinite = True
if infinite:
    print "INFINITE PATHS"
else:
    print paths.count