def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    T = int(input[idx]); idx +=1

    pre_compute = [0] * N
    for _ in range(M):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        pre_compute[a] |= (1 << b)

    current = 1 << 0  # initial state: only vertex 0
    if T == 0:
        # No steps, answer is 1
        print(1)
        return

    seen = {}
    history = []
    step = 0
    seen[current] = step
    history.append(current)

    found_cycle = False
    cycle_start = 0
    cycle_length = 0

    while step < T:
        next_nodes = 0
        for v in range(N):
            if (current >> v) & 1:
                next_nodes |= pre_compute[v]
        current = next_nodes
        step += 1

        if current == 0:
            break  # cannot proceed further

        if current in seen:
            prev_step = seen[current]
            cycle_length = step - prev_step
            remaining = T - step
            remaining %= cycle_length
            step = T - remaining
            # Jump to near the end, then simulate remaining steps
            found_cycle = True
            break
        else:
            seen[current] = step
            history.append(current)
            if step == T:
                break

    if not found_cycle:
        # Need to simulate until step reaches T
        while step < T:
            next_nodes = 0
            for v in range(N):
                if (current >> v) & 1:
                    next_nodes |= pre_compute[v]
            current = next_nodes
            step += 1
            if current == 0:
                break

    count = bin(current).count('1') if current != 0 else 0
    print(count)

if __name__ == "__main__":
    main()