Problem name: Tester

Problem ID: 19006

Problem setter: Vlad Dascalu

Problem input: standard input

Problem output: standard output

Background:

John and Vlad decide to make M swaps inside a vector with N numbers, from 1 to N. A swap consists in taking two indexes, i and j, and switch between them the values of V[i] and V[j] (where V is the vector containing the N numbers) if V[i] > V[j].

Problem:

Based on the swaping sequence, determine if the algorithm orders the vector correctly (from the smallest number to the biggest), no matter the initial order.

Input data:

On the first line we can find M and N separated by a space. Each of the following lines contains two indices, i and j. If V[i] > V[j], the values are switched between them.

Output data:

1 if V comes sorted, no matter the original pattern. 0 otherwise.

Example:

input:

6 4
1 2
2 3
3 4
1 2
2 3
1 2

output:

1

Restrictions:

1