컴퓨터 운영체제에서는 여러 프로세스들이 서로가 가진 자원을 기다리며 무한히 대기하는 '교착 상태(Deadlock)' 현상이 발생할 수 있습니다.

이를 관리하기 위해 시스템의 자원 할당 상태를 "방향 그래프"로 표현하여 감시합니다.

프로세스 A가 프로세스 B의 자원을 기다리는 상황은 A에서 B로 향하는 방향 간선으로 나타냅니다.

만약 이 방향 그래프 내부에서 순환 구조, 즉 '사이클(Cycle)'이 발생한다면 시스템에 교착 상태가 존재함을 의미합니다.

시스템의 프로세스 개수 N과 프로세스 간의 대기 관계를 나타내는 방향 간선 정보가 주어질 때, 시스템에 교착 상태가 존재하는지 여부를 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 프로세스의 개수 N과 대기 관계의 개수 M이 공백을 사이에 두고 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000)

다음 M개의 줄에는 방향 간선의 시작점 u와 도착점 v가 공백을 사이에 두고 주어진다. 이는 u번 프로세스가 v번 프로세스의 자원을 대기하고 있음(u -> v)을 의미합니다.

그래프에 동일한 간선이 중복되어 주어질 수 있으며, 자기 자신을 가리키는 간선이 주어질 수도 있습니다.

출력

주어진 방향 그래프에 사이클이 존재하여 교착 상태가 발생했다면 1을, 사이클이 전혀 없어 안전하다면 0을 출력한다.

제약 조건

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 200,000
• 1 ≤ u, v ≤ N

예제 입력 1

4 4
1 2
2 3
3 4
4 2

예제 출력 1

1

예제 입력 2

3 2
1 2
2 3

예제 출력 2

0

예제 입력 3

4 4
1 2
1 3
2 3
2 4

예제 출력 3

0