#include #include #include using namespace std; // ???????????????????????? bool chordsIntersect(int n, int a, int b, int c, int d) { // ??a < b?c < d???????? if (a > b) swap(a, b); if (c > d) swap(c, d); // ??1???????? if (a == c && b == d) return true; // ??2?????? if (a == c || a == d || b == c || b == d) return true; // ??3????????? // ????????(a, b, c, d)???????? // ??????(c?d?????a-b??????b-a??) // ????????a???0 int b1 = (b - a + n) % n; int c1 = (c - a + n) % n; int d1 = (d - a + n) % n; // ??a=0?b=b1??0 < b1 < n // ??c1?d1?????(0, b1)??????(b1, n)?? bool c_in_range = (0 < c1 && c1 < b1); bool d_in_range = (0 < d1 && d1 < b1); return (c_in_range != d_in_range); } // ??????????????? bool chordsIntersect2(int n, int a, int b, int c, int d) { // ????????????????? vector indices = {a, b, c, d}; // ????????????????????? // ??????????????????????????????? // ????????x????(from, to)???????????? auto isOnArc = [n](int from, int to, int x) -> bool { if (from == to) return false; if (from < to) { return from < x && x < to; } else { // ??????? return (from < x && x < n) || (0 <= x && x < to); } }; // ??c?d??????(a, b)??????(b, a)? bool c_in_ab = isOnArc(a, b, c); bool d_in_ab = isOnArc(a, b, d); if (c_in_ab != d_in_ab) { return true; // ???? } // ??a?b??????(c, d)??????(d, c)? bool a_in_cd = isOnArc(c, d, a); bool b_in_cd = isOnArc(c, d, b); if (a_in_cd != b_in_cd) { return true; // ???? } // ????????? if (a == c || a == d || b == c || b == d) { return true; // ???? } return false; } // ???? int main() { //chordsIntersect(8, 0, 4, 1, 5) ; int n,m; cin>>n>>m; int cnt=0; int k[100010][2]; for(int i=0;i>k[i][0]>>k[i][1]; } for(int i=0;i