Problem name: Tester

Problem ID: 19006

Problem setter: Vlad Dascalu

Problem input: standard input

Problem output: standard output


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].


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.



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