• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

مربّاها که از حل معما خوششان آمده بود، از بزرگشان خواستند که معمای دیگری به آن‌ها بگوید. بزرگ مربّاها پس از کمی فکر این معما را برای مربّاها مطرح کرد:

یک مثلث قائم‌الزاویه \(n \times n\) داریم. مثلث از \(n\) ستون تشکیل شده که ستون \(i\)ام آن، \(n - i\) سطر دارد. در \(m\) تا از خانه‌های مثلث مربّا و در بقیه خانه‌های آن عسل قرار داده شده است. یک زیرمثلث \(k\)تایی نشان‌گر اشتراک خانه‌های \(k\) سطر و \(k\) ستون متناظر آن‌ها از مثلث است. یک زیرمثلث خوب، زیرمثلثی‌است که در تمام خانه‌های آن مربّا قرار دارد. همچنین زیرمثلث دوست‌داشتنی زیر‌مثلثی‌است که به ازای هر سطر آن، در اجتماع خانه‌های آن سطر و ستون متناظرش دو مربّا وجود داشته باشد. علاوه بر این یک زیرمثلث عجیب، زیرمثلثی‌ است که دوست‌داشتنی باشد، ولی هیچ زیرمثلثی از آن دوست‌داشتنی نباشد.

تعداد زیرمثلث‌های \(k\)تایی خوب مثلث برابر با \(f(k)\) است. بزرگ مربّاها از آن‌ها خواست تا مقدار \[\Sigma_{i = 1}^n f(i) \times (-1)^{i+1}\] را بیابند. مربّاها که از شنیدن این معما گیج شده بودند، از بزرگ مربّاها خواستند تا کمکی به آن‌ها بکند. بزرگ مربّاها کمی فکر کرد و سپس به مربّاها گفت که کاری می‌کند که اگر زیرمثلث \(k\)تایی عجیب در مثلث بود، \(k \leq 3\) باشد.

مربّاها بعد از این که بزرگشان این شرط را روی مثلث گذاشت، باز هم نتوانستند مسئله را حل کنند، برای همین باز هم دست به دامن شما شدند. لطفا به آن‌ها کمک کنید تا مسئله را حل کنند.

ورودی

در اولین خط ورودی، \(n\) که نشان‌دهنده‌ی اندازه‌ی مثلث است و \(m\) که تعداد مربّاهای داخل مثلث است، می‌آید. در ادامه \(m\) خط می‌آید که در خط \(i\)ام، \(r_i\) و \(c_i\) آمده است که به ترتیب سطر و ستون خانه‌ی مربّای \(i\)ام را نشان می‌دهد. \[1 \leq n \leq 100\ 000\] \[0 \leq m \leq 1000\ 000\] \[1 \leq c_i < r_i \leq n\]

خروجی

در تنها خط خروجی، مقداری که بزرگ مربّا در معما خواسته را خروجی دهید.

مثال

ورودی نمونه ۱

3 2
1 2
1 3

خروجی نمونه ۱

1

مجموعه شماره سطرهایی که زیرمثلث خوب می‌سازند عبارتند از:

• \(\{1\}\)
• \(\{2\}\)
• \(\{3\}\)
• \(\{1, 2\}\)
• \(\{1, 3\}\)