A logistics network has n facilities, numbered 1 to n, and m one-way shipping routes. A route u v means product can flow directly from facility u to facility v (but not necessarily the other way). Product can also flow through any number of intermediate facilities by chaining routes.

Given a source facility and a destination facility, determine whether a product can be shipped from the source to the destination (a facility can always "ship to itself" with zero hops).

Input format

Line 1: two integers n and m — number of facilities (1-indexed) and number of routes. Next m lines: two integers u v — a directed route from facility u to facility v. Last line: two integers src dst — the source and destination facilities.

Output format

A single integer: 1 if dst is reachable from src, 0 otherwise.

Constraints

• 1 ≤ n ≤ 40
• 0 ≤ m ≤ 200
• 1 ≤ u, v, src, dst ≤ n

4 3
1 2
2 3
3 4
1 4

1

3 1
2 3
1 3

0