Counting Paths with Exactly k Edges

You are given a directed graph with n vertices numbered from 1 to n and m directed edges. Your task is to determine the number of unique paths from vertex 1 to vertex n that use exactly k edges.

Let \( dp[v][i] \) denote the number of ways to reach vertex \( v \) using exactly \( i \) edges. The recurrence relation is:

\( dp[v][i] = \sum_{u \in \text{pred}(v)} dp[u][i-1] \)

with the base case \( dp[1][0] = 1 \). Use dynamic programming to compute the answer.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains three integers \( n \), \( k \), and \( m \), representing the number of vertices, the exact number of edges to be used in the path, and the number of directed edges, respectively.
• The next \( m \) lines each contain two integers \( u \) and \( v \) indicating that there is a directed edge from vertex \( u \) to vertex \( v \).

outputFormat

Output a single integer via standard output (stdout): the number of unique paths from vertex 1 to vertex \( n \) that contain exactly \( k \) edges.

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

2