头像

acwing_kai




离线:12小时前



acwing_kai
14小时前

树状数组

区间修改 区间查询

前缀和 差分

/**
 * 树状数组
 * 区间修改 区间查询
 * 前缀和 差分
 */
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100005;
typedef long long ll;
int n, m;
ll sum[maxn], t1[maxn], t2[maxn];

void add1(int x, ll k){
    for(; x <= n; x += x & -x) t1[x] += k;
}

ll ask1(int x){
    ll ans = 0;
    for(; x; x -= x & -x) ans += t1[x];
    return ans;
}

void add2(int x, ll k){
    for(; x <= n; x += x & -x) t2[x] += k;
}

ll ask2(int x){
    ll ans = 0;
    for(; x; x -= x & -x) ans += t2[x];
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1, x; i <= n; ++ i){
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    while(m --){
        char op;
        int l, r;
        ll z;
        cin >> op;
        if(op == 'Q'){
            cin >> l >> r;
            ll ans = sum[r] + (r + 1) * ask1(r) - ask2(r);
            ans -= sum[l - 1] + l * ask1(l - 1) - ask2(l - 1);
            cout << ans << endl;
        }else{
            cin >> l >> r >> z;
            add1(l, z);
            add1(r + 1, -z);
            add2(l, l * z);
            add2(r + 1, - (r + 1) * z);
        }
    }

    return 0;
}

线段树 lazy标记

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
    int l, r;
    ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){t[p].sum = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

void spread(int p){
    if(t[p].lazy){
        t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
        t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
        t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
        t[2 * p + 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void change(int p, int l, int r, ll d){
    if(t[p].l >= l && t[p].r <= r) {
        t[p].sum += d * (t[p].r - t[p].l + 1);
        t[p].lazy += d;  //注意是 "+=" 不是 "="
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(2 * p, l, r, d);
    if(r > mid) change(2 * p + 1, l, r, d);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
   if(t[p].l >= l && t[p].r <= r) return t[p].sum;
   int mid = t[p].l + t[p].r >> 1;
   spread(p);
   ll res = 0;
   if(l <= mid) res += ask(2 * p, l, r);
   if(r > mid) res += ask(2 * p + 1, l, r);
   return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    build(1, 1, n);

    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << ask(1, l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(1, l, r, val);
        }
    }
    return 0;
}

分块

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100005;
int n, m, t;
ll a[maxn], sum[maxn], add[maxn];
int L[maxn], R[maxn], pos[maxn];

void change(int l, int r, ll d){
    int lpos = pos[l], rpos = pos[r];
    if(lpos == rpos){
        for(int i = l; i <= r; ++ i) a[i] += d;
        sum[lpos] += (r - l + 1) * d;
    }else{
        for(int i = l; i <= R[lpos]; ++ i) a[i] += d;
        sum[lpos] += (R[lpos] - l + 1) * d;
        for(int i = L[rpos]; i <= r; ++ i) a[i] += d;
        sum[rpos] += (r - L[rpos] + 1) * d;
        for(int i = lpos + 1; i < rpos; ++ i) add[i] += d;
    }
}

ll query(int l, int r){
    ll ret = 0;
    int lpos = pos[l], rpos = pos[r];
    if(lpos == rpos){
        for(int i = l; i <= r; ++ i) ret += a[i];
        ret += add[lpos] * (r - l + 1);
    }else{
        for(int i = lpos + 1; i < rpos; ++ i) ret += sum[i] + (R[i] - L[i] + 1) * add[i];
        for(int i = l; i <= R[lpos]; ++ i) ret += a[i];
        ret += add[lpos] * (R[lpos] - l + 1);
        for(int i = L[rpos]; i <= r; ++ i) ret += a[i];
        ret += add[rpos] * (r - L[rpos] + 1);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    //分块
    t = sqrt(n);
    for(int i = 1; i <= t; ++ i){
        L[i] = (i - 1) * sqrt(n) + 1;
        R[i] = i * sqrt(n);
    }
    if(R[t] < n){
        L[t + 1] = R[t] + 1;
        R[t + 1] = n;
        t ++;
    }
    //预处理
    for(int i = 1; i <= t; ++ i){
        for(int j = L[i]; j <= R[i]; ++ j){
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    //solve
    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(l, r, val);
        }
    }
}


活动打卡代码 AcWing 248. 窗内的星星

/**
 * 线段树
 * 扫描线
 * Lazy标记
 */

#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 100005;
int n, w, h, m;

struct Edge{
    int x1, x2, y;
    int val;
    bool operator < (const Edge &tmp) const{
        if(y != tmp.y) return y < tmp.y;
        else return val < tmp.val; //可重叠 应先计算减少的再计算增加的
    }
}e[maxn * 2];

struct SegmentTree{
    int l, r, maxx, lazy;
}t[maxn * 8];

int XList[maxn * 2];
int query(int x){
    return lower_bound(XList, XList + m, x) - XList;
}

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r, t[p].maxx = t[p].lazy = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
}

void spread(int p){
    if(t[p].lazy){
        t[2 * p].maxx += t[p].lazy;
        t[2 * p + 1].maxx += t[p].lazy;
        t[2 * p].lazy += t[p].lazy;
        t[2 * p + 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void change(int p, int l, int r, int val){
    if(l <= t[p].l && t[p].r <= r){
        t[p].maxx += val;
        t[p].lazy += val;
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(2 * p, l, r, val);
    if(r > mid) change(2 * p + 1, l, r, val);

    t[p].maxx = max(t[2 * p].maxx, t[2 * p + 1].maxx);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n >> w >> h){
        int x, y, c, cnt = 0;
        for(int i = 0; i < n; ++ i){
            cin >> x >> y >> c;
            e[cnt] = {x, x + w - 1, y, c};
            XList[cnt ++] = x;
            e[cnt] = {x, x + w - 1, y + h - 1, -c};
            XList[cnt ++] = x + w - 1;
        }

        sort(XList, XList + cnt);
        sort(e, e + cnt);

        m = unique(XList, XList + cnt) - XList;
        build(1, 0, m - 1);
        int ans = 0;
        for(int i = 0; i < cnt; ++ i){
            int el = query(e[i].x1);
            int er = query(e[i].x2);
            change(1, el, er, e[i].val);
            ans = max(ans, t[1].maxx);
        }
        cout << ans << endl;
    }
}


活动打卡代码 AcWing 247. 亚特兰蒂斯

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100005;

struct Edge{
    double x1, x2, y;
    int op;
    bool operator < (const Edge &tmp) const{
        return y < tmp.y;
    }
}e[maxn * 2];

struct SegmentTree{
    int l, r, cnt;
    double len;
}t[maxn * 4];

int n, m, T;
double xList[maxn * 2];

int query(double x){
    return lower_bound(xList, xList + m, x) - xList;
}

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r, t[p].cnt = t[p].len = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
}

void get_len(int p){
    if(t[p].cnt >= 1) t[p].len = xList[t[p].r + 1] - xList[t[p].l];
    else t[p].len = t[p << 1].len + t[(p << 1) | 1].len;
}

void update(int p, int l, int r, int val){
    if(l <= t[p].l && t[p].r <= r){
        t[p].cnt += val;
        get_len(p);
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) update(2 * p, l, r, val);
    if(r > mid) update(2 * p + 1, l, r, val);
    get_len(p);
}

int main(){
    T = 1;
    while(scanf("%d",&n), n){
        double x1, y1, x2, y2;
        int cnt = 0;
        for(int i = 0; i < n; ++ i){
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            e[cnt] = {x1, x2, y1, 1};
            xList[cnt ++] = x1;
            e[cnt] = {x1, x2, y2, -1};
            xList[cnt ++] = x2;
        }

        sort(xList, xList + cnt);
        sort(e, e + cnt);
        m = unique(xList, xList + cnt) - xList;

        build(1, 0, m - 1);

        double ans = 0;
        for(int i = 0; i < cnt - 1; ++ i){
            int el = query(e[i].x1);
            int er = query(e[i].x2) - 1;
            update(1, el, er, e[i].op);
            ans += (e[i + 1].y - e[i].y) * t[1].len;
        }

        printf("Test case #%d\n", T ++);
        printf("Total explored area: %.02f\n\n", ans);
    }
    return 0;
}



线段树基本操作

struct SegmentTree {
    int l, r;
    int dat;
}t[maxn * 4];

//1. 线段树的建树
void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){ t[p].dat = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].dat = max(d[p * 2].dat, d[p * 2 + 1].dat);
}

build(1, 1, n);

//2. 线段树的单点修改
void change(int p, int x, int v){
    if(t[p].l == t[p].r){ t[p].dat = v; return;}
    int mid = (t[p].l + r[p].r) / 2;
    if(x <= mid) change(p * 2, x, v);
    else change(p * 2 + 1, x, v);
    t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);
}

change(1, x, n);

//3. 线段树的区间查询
int ask(int p, int l, int r){
    if(l <= t[p].l && t[p].r <= r) return t[p].dat;
    int mid = t[p].l + t[p].r >> 1;
    int res = -(1 << 30);
    if(l <= mid) res = max(res, ask(2 * p, l, r));
    if(r > mid) res = max(res, ask(2 * p + 1, l, r));
    return res;
}
cout << ask(1, l, r) << endl;

延迟标记 lazy标记 Acwing.243

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
    int l, r;
    ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){t[p].sum = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

void spread(int p){
    if(t[p].lazy){
        t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
        t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
        t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
        t[2 * p + 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void change(int p, int l, int r, ll d){
    if(t[p].l >= l && t[p].r <= r) {
        t[p].sum += d * (t[p].r - t[p].l + 1);
        t[p].lazy += d;  //注意是 "+=" 不是 "="
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(2 * p, l, r, d);
    if(r > mid) change(2 * p + 1, l, r, d);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
   if(t[p].l >= l && t[p].r <= r) return t[p].sum;
   int mid = t[p].l + t[p].r >> 1;
   spread(p);
   ll res = 0;
   if(l <= mid) res += ask(2 * p, l, r);
   if(r > mid) res += ask(2 * p + 1, l, r);
   return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    build(1, 1, n);

    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << ask(1, l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(1, l, r, val);
        }
    }
    return 0;
}

扫描线例题 Acwing 247

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100005;

struct Edge{
    double x1, x2, y;
    int op;
    bool operator < (const Edge &tmp) const{
        return y < tmp.y;
    }
}e[maxn * 2];

struct SegmentTree{
    int l, r, cnt;
    double len;
}t[maxn * 4];

int n, m, T;
double xList[maxn * 2];

int query(double x){
    return lower_bound(xList, xList + m, x) - xList;
}

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r, t[p].cnt = t[p].len = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
}

void get_len(int p){
    if(t[p].cnt >= 1) t[p].len = xList[t[p].r + 1] - xList[t[p].l];
    else t[p].len = t[p << 1].len + t[(p << 1) | 1].len;
}

void update(int p, int l, int r, int val){
    if(l <= t[p].l && t[p].r <= r){
        t[p].cnt += val;
        get_len(p);
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) update(2 * p, l, r, val);
    if(r > mid) update(2 * p + 1, l, r, val);
    get_len(p);
}

int main(){
    T = 1;
    while(scanf("%d",&n), n){
        double x1, y1, x2, y2;
        int cnt = 0;
        for(int i = 0; i < n; ++ i){
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            e[cnt] = {x1, x2, y1, 1};
            xList[cnt ++] = x1;
            e[cnt] = {x1, x2, y2, -1};
            xList[cnt ++] = x2;
        }

        sort(xList, xList + cnt);
        sort(e, e + cnt);
        m = unique(xList, xList + cnt) - xList;

        build(1, 0, m - 1);

        double ans = 0;
        for(int i = 0; i < cnt - 1; ++ i){
            int el = query(e[i].x1);
            int er = query(e[i].x2) - 1;
            update(1, el, er, e[i].op);
            ans += (e[i + 1].y - e[i].y) * t[1].len;
        }

        printf("Test case #%d\n", T ++);
        printf("Total explored area: %.02f\n\n", ans);
    }
    return 0;
}


活动打卡代码 AcWing 116. 飞行员兄弟

#include <bits/stdc++.h>

using namespace std;

int state, now, ans, res;

void change(int pos){
//    for(int i = 0; i < 16; ++ i) cout << (now >> i & 1) << " ";
//    cout << endl;

    int x = pos / 4, y = pos % 4;
    for(int i = 0; i < 4; ++ i){
        int p = x * 4 + i;
        now = now ^ (1 << p);
    }

    for(int i = 0; i < 4; ++ i){
        int p = 4 * i + y;
        now = now ^ (1 << p);
    }
    now = now ^ (1 << pos);

//    for(int i = 0; i < 16; ++ i) cout << (now >> i & 1) << " ";
//    cout << endl;
}

int main(){
    for(int i = 0; i < 4; ++ i){
        string s;
        cin >> s;
        for(int j = 0; j < 4; ++ j){
            if(s[j] == '+') state += (1 << (i * 4 + j));
        }
    }

    ans = 0x3f3f3f3f;
    for(int i = 0; i < (1 << 16); ++ i){
        now = state;
        int cnt = 0;
        for(int j = 0; j < 16; ++ j){
            if(i >> j & 1) cnt ++, change(j);
        }
        if(now == 0){
            if(cnt < ans){
                ans = cnt;
                res = i;
            }
        }
    }

    cout << ans << endl;
    for(int i = 0; i < 16; ++ i)
        if(res >> i & 1) cout << (i / 4) + 1 << " " << (i % 4) + 1 << endl;
    return 0;
}


活动打卡代码 AcWing 373. 車的放置

acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 205;
bool unreach[maxn][maxn], vis[maxn];
int match[maxn];
int n, m, t;

bool dfs(int x){
    for(int i = 1; i <= m; ++ i){
        if(!vis[i] && !unreach[x][i]){
            vis[i] = 1;
            if(match[i] == 0 || dfs(match[i])){
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> m >> t;
    for(int i = 0, x, y; i < t; ++ i){
        cin >> x >> y;
        unreach[x][y] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans ++;
    }
    cout << ans << endl;
}



acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 105;
int n, t;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool valid[maxn][maxn], vis[maxn][maxn];
int match[maxn][maxn]; //match = xxxxxx = x * 1000 + y

bool ok(int x, int y){
    if(x >= 1 && x <= n && y >= 1 && y <= n && valid[x][y] == 0) return true;
    return false;
}

bool dfs(int x, int y){
    for(int i = 0; i < 4; ++ i){
        int xx = x + dx[i], yy = y + dy[i];
        if(ok(xx,yy) && vis[xx][yy] == 0){
            vis[xx][yy] = 1;
            if(match[xx][yy] == 0 || dfs(match[xx][yy] / 1000, match[xx][yy] % 1000)){
                match[xx][yy] = x * 1000 + y;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> t;
    for(int i = 1, x, y; i <= t; ++ i){
        cin >> x >> y;
        valid[x][y] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            if((i + j) % 2 == 0 && valid[i][j] == 0){
                memset(vis, 0, sizeof(vis));
                if (dfs(i, j)) ans++;
            }

    cout << ans << endl;
}


活动打卡代码 AcWing 372. 棋盘覆盖

acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 105;
int n, t;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool valid[maxn][maxn], vis[maxn][maxn];
int match[maxn][maxn]; //match = xxxxxx = x * 1000 + y

bool ok(int x, int y){
    if(x >= 1 && x <= n && y >= 1 && y <= n && valid[x][y] == 0) return true;
    return false;
}

bool dfs(int x, int y){
    for(int i = 0; i < 4; ++ i){
        int xx = x + dx[i], yy = y + dy[i];
        if(ok(xx,yy) && vis[xx][yy] == 0){
            vis[xx][yy] = 1;
            if(match[xx][yy] == 0 || dfs(match[xx][yy] / 1000, match[xx][yy] % 1000)){
                match[xx][yy] = x * 1000 + y;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> t;
    for(int i = 1, x, y; i <= t; ++ i){
        cin >> x >> y;
        valid[x][y] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            if((i + j) % 2 == 0 && valid[i][j] == 0){
                memset(vis, 0, sizeof(vis));
                if (dfs(i, j)) ans++;
            }

    cout << ans << endl;
}



acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 10005, maxm = 200005;
int n, m, e, tot, ans;
int head[maxn], ver[maxm], Next[maxm], match[maxn];
bool vis[maxn];
void add(int x, int y){
    ver[++ tot] = y;
    Next[tot] = head[x], head[x] = tot;
}

bool dfs(int x){
    for(int i = head[x], y; i; i = Next[i]){
        if(!vis[y = ver[i]]){
            vis[y] = 1;
            if(!match[y] || dfs(match[y])){
                match[y] = x; return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> m >> e;
    for(int i = 1, x, y; i <= e; ++ i){
        cin >> x >> y;
        add(x, y + n);
        add(y + n, x);
    }

    for(int i = 1; i <= n; ++ i){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans ++;
    }

    cout << ans << endl;
}



acwing_kai
1个月前
    //染色法判断二分图
#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 20005, maxm = 100005;
int head[maxn], ver[2 * maxm], Next[2 * maxm], tot, v[maxn];

void add(int x, int y){
    ver[++ tot] = y;
    Next[tot] = head[x], head[x] = tot;
}

bool dfs(int x, int color){
    v[x] = color;
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i];
        if(!v[y]){
            bool flag = dfs(y, 3 - color);
            if(!flag) return false;
        }
        else if(v[y] == color) return false;
    }
    return true;
}

bool check(){
    memset(v, 0, sizeof(v));
    for(int i = 1; i <= n; ++ i)
        if(!v[i])
            if(!dfs(i, 1)) return false;
    return true;
}

int main()
{
    cin >> n >> m;

    for(int i = 1, x, y; i <= m; ++i){
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    cout << check() <<endl;
    return 0;
}


/**
5 5
1 4
2 3
2 5
4 5
1 3
*/