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

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

4

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

2