Exactly k links away

Problem

Offices are joined by two-way links. Print how many offices are exactly k links away from office s, taking the fewest links needed to reach each office.

Input, output and limits

Input: Line 1: n and m, the number of nodes and edges. Then m lines, each with two node numbers a and b for a two-way link. Nodes are numbered 0 to n - 1. The last line has s and k.
Output: One integer.
Constraints: 1 ≤ n ≤ 100000
0 ≤ m ≤ 200000
No node is linked to itself and no pair is listed twice
0 ≤ s < n
0 ≤ k ≤ n

Examples

Example

Input

Output

Only office 3 is two links away.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Run BFS to get the distance of every node.

Hint 2

Count the nodes whose distance equals k.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Largest land patchmedium
Split into two teamsmedium
Shortest way through the mazemedium
Print the shortest routemedium
Tasks that wait for each othermedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems