Jason's luck has finally run out. After a late night coding session, he realizes he's been locked out from engineering maths building, again. Unfortunately, Shahid is the only one who can open the doors from the inside.

However, the building's automatic security system is not simple. To unlock the final door, Shahid must open a specific set of inner doors first and each door may depend on others being opened before it.

Each door is represented by a node in a directed graph. If door u must be opened before door v, there is a directed edge from u to v. Shahid must find an order in which all doors can be opened without violating any dependency.

But there's a catch! Some dependencies may form cycles, meaning the system is jammed and no valid sequence exists. In that case, Jason's sleeping outside tonight.

Help Shahid determine whether it's possible to open all doors to let Jason in.

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5)~ the number of doors and the number of dependency relations.

The next ~m~ lines each contain two integers ~u~ ~v~ ~(1 \leq u, v \leq n, u \neq v)~, meaning door ~u~ must be opened before door ~v~.

Output

If it's impossible to open all doors due to circular dependencies, print:

Jason is sleeping outside tonight.

Otherwise, print:

Shahid can let Jason in.

Example

Input 1

4 3
1 2
2 3
1 4

Output 1

Shahid can let Jason in.

Explanation:

• Door 1 must be opened before doors 2 and 4.
• Door 2 must be opened before door 3.
• A valid sequence is 1 2 4 3.

Input 2

3 3
1 2
2 3
3 1

Output 1

Jason is sleeping outside tonight.

Explanation:

• The system forms a cycle: 1 -> 2 -> 3 -> 1
• There's no way to open all of the doors, as to open door 2, you need to open door 1, and to open door 1, you need to open door 2.