A relay network has n nodes numbered 1 through n, joined by bidirectional links. A broadcast starts at a source node s and travels across links; reaching a neighbor costs one hop. A node's hop-distance from s is the minimum number of links on any path from s to it.
Given the source s and a hop budget K, count how many nodes other than s have hop-distance at most K from s. Nodes with no path from s are never counted.
Input format
Line 1: two integers n and m.
Next m lines: two integers u and v, a bidirectional link between nodes u and v.
Last line: two integers s and K.
Output format
A single integer: the number of nodes (excluding s) reachable within K hops.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 1 <= u, v, s <= n and 0 <= K <= 10^9