يريد Farmer John تجميع صورة بانورامية لصف من $N$ أبقار ($(1 \le N \le 200,000)$)، مرقمة كالمعتاد من $1..N$. التقط $M$ صور ($(1 \le M \le 100,000)$)، تغطي كل منها نطاقًا متصلًا: الصورة $i$ تحتوي الأبقار من $a_i$ إلى $b_i$ شاملًا الطرفين. لا يلزم أن تغطي الصور مجتمعة كل بقرة.

لاحظ FJ أن كل صورة تحتوي بالضبط بقرة واحدة ذات بقع! كان يعرف أن في القطيع بعض الأبقار المرقطة لكنه لم يعدها. حدد أكبر عدد ممكن منها وفق الصور. إذا لم يمكن توزيع البقع على الأبقار بما يوافق جميع الصور، اطبع $-1$.

الإدخال

• السطر $1$: العددان الصحيحان $N$ و$M$.

• الأسطر $2..M+1$: السطر $i+1$ يحتوي $a_i$ و$b_i$.

الإخراج

• السطر $1$: أكبر عدد ممكن من الأبقار المرقطة، أو $-1$ إذا لا يوجد حل.

أمثلة

الإدخال 1

5 3
1 4
2 5
3 4

الإخراج 1

1

ملاحظة

توجد $5$ أبقار و$3$ صور. تحتوي الأولى الأبقار من $1$ إلى $4$، وهكذا.

تبين الصورة الأخيرة أن البقرة $3$ أو $4$ يجب أن تكون مرقطة. اختيار أي منهما يحقق أيضًا الصورتين الأوليين.

مؤلف المسألة: Brian Dean، 2013