Reachable Vertices in Exactly k Steps

You are given a directed graph with n vertices numbered from 1 to n and m edges. Each edge connects one vertex to another. Given a starting vertex v and an integer k, your task is to compute the number of distinct vertices that can be reached from v by traversing exactly k edges.

Formally, for a given directed graph \(G = (V, E)\) where \(V = \{1,2,\ldots,n\}\) and \(E\) is a set of directed edges, determine the number of vertices \(u \in V\) such that there exists a path: \[ v \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow u \] with exactly \(k\) edges.

If k = 0, the only vertex reachable is the starting vertex itself.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 u1 w1
 u2 w2
 ...
 um wm
 v k

Where:

• n is the number of vertices.
• m is the number of edges.
• Each of the next m lines contains two integers u and w representing an edge from vertex u to vertex w.
• The last line contains two integers: the starting vertex v and the number of steps k.

outputFormat

Output a single integer to standard output (stdout), which is the number of vertices reachable from v in exactly k steps.

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

1