Longest Path in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with n vertices and m edges. Each edge is directed from vertex u to vertex v. Additionally, you are given q queries; each query provides a starting vertex. For each query, determine the length of the longest path starting from that vertex. The length of a path is defined as the number of vertices on the path.

Note: If the starting vertex has no outgoing edges, then the longest path consists of the vertex itself (and its length is 1). It is guaranteed that the input graph contains no cycles.

Hint: You can solve this problem using a topological sort followed by dynamic programming. Recall that in LaTeX the recurrence for the longest path can be written as:

$$dp[u] = \max_{(u,v) \in E} \{ 1 + dp[v] \}, \quad dp[u] = 1 \text{ if } u \text{ is a terminal node.} $$

inputFormat

The input is given from standard input and contains the following:

• The first line contains two integers n and m — the number of vertices and edges.
• The next m lines each contain two integers u and v representing a directed edge from u to v.
• The following line contains a single integer q — the number of queries.
• The last line contains q integers, each representing a starting vertex for which you must calculate the longest path length.

outputFormat

For each query, output a single integer representing the length of the longest path starting from the given vertex. The answers for the queries should be printed in one line separated by a single space.

## sample

5 6
1 2
1 3
2 4
2 5
3 4
4 5
3
1 2 3

4 3 3