How far does the news spread?

Problem

In a social app, a post is shared along one-way follow links: a link a to b means b sees what a shares. Starting with user s, count how many users end up seeing the post, including s.

Input, output and limits

Input: Line 1: n and m, the number of nodes and one-way links. Then m lines, each with a and b for a link from a to b. Nodes are numbered 0 to n - 1. The last line has s.
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

Examples

Example

Input

Output

Users 0, 1 and 2 see it. User 3 follows 2 but nobody shares to 3.

Hints

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

Hint 1

The links have a direction: only follow them from a to b.

Hint 2

Search from s and count the nodes you mark.

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

Solve in the editor

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