vector<vector<int> > graph;
vector<int> inDegree; // index 노드에서 갈 수 있는 노드의 개수
vector<int> result; // 정점을 방문하는 순서

// 진입 차수가 0인 노드를 큐에 삽입합니다
queue<int> q;
for (int node = 1; node <= N; node++) {
  if (inDegree[node] == 0) {
    q.push(node);
  }
}

// 정렬이 완전히 수행되려면 N개의 노드를 전부 방문합니다
for(int index = 0; index < N; index++) {
  if(q.empty()) {
    // n개를 방문하기 전에 큐가 비어버리면 사이클이 발생한 것
    // (이전에 진입차수가 0인 정점이 없었다는 의미이므로)
    break;
  }

  int cur = q.front();
  q.pop();
  result[index] = cur;

  for(int next : graph[cur]) {
    inDegree[next]--;

    // 새롭게 진입차수가 0이 된 정점을 큐에 삽입합니다
    if(inDegree[next] == 0) {
      q.push(next);
    }
  }
}

// costs : 해당 index까지 방문하는데 들어가는 최소 비용
// times 각 정점의 비용 (이전 정점에서 현재 정점까지 도달하는 데 비용)
vector<int> costs, times;
for (int node = 1; node <= N; node++) {
  costs[node] = times[node] = cost;
}

// 모든 노드를 방문하지 않아도 됨
while (!q.empty()) {
  int cur = q.front();
  q.pop();

  for (int next : graph[cur]) {
    times[next] = max(times[next], costs[next] + times[cur]);

    inDegree[next] -= 1;
    if (inDegree[next] == 0) {
      q.push(next);
    }
  }
}

for (int node = 1; node <= N; node++) {
  answer = max(answer, times[node]);
}