def main():
    import sys
    N, M, T = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        edges[a].append(b)
    
    if T == 0:
        print(1)
        return
    
    out_degree = [len(es) for es in edges]
    if out_degree[0] == 0:
        print(0)
        return
    
    # Precompute the mask for each vertex u: pre[u] is the mask of reachable vertices in one step
    pre = [0] * N
    for u in range(N):
        if out_degree[u] == 0:
            pre[u] = 0
        else:
            mask = 0
            for v in edges[u]:
                mask |= 1 << v
            pre[u] = mask
    
    current_mask = 1 << 0  # initial mask is only vertex 0
    history = {current_mask: 0}
    masks = [current_mask]
    step = 0
    found_cycle = False
    cycle_start = 0
    cycle_length = 0
    
    while step < T:
        new_mask = 0
        mask = current_mask
        while mask:
            lsb = mask & -mask
            u = (lsb).bit_length() - 1
            new_mask |= pre[u]
            mask ^= lsb
        
        step += 1
        current_mask = new_mask
        if current_mask in history:
            # Found a cycle
            cycle_start = history[current_mask]
            cycle_length = step - cycle_start
            found_cycle = True
            break
        history[current_mask] = step
        masks.append(current_mask)
        if current_mask == 0:
            break  # No further steps possible
    
    if found_cycle:
        remaining_steps = T - cycle_start
        remaining = remaining_steps % cycle_length
        final_step = cycle_start + remaining
        if final_step < len(masks):
            current_mask = masks[final_step]
        else:
            idx_in_cycle = (final_step - cycle_start) % cycle_length
            current_mask = masks[cycle_start + idx_in_cycle]
    elif step < T:
        # This means current_mask became 0 before T steps
        pass
    
    print(bin(current_mask).count('1'))

if __name__ == '__main__':
    main()