记录编号	334697	评测结果	AAAAATAAAT
题目名称	MAX-2-SAT	最终得分	80
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	3.953 s
提交时间	2016-11-01 15:41:23	内存使用	0.29 MiB

//KZNS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
int head[53];
int id[406];
int next[406];
int ls[203][2];
bool re[203][2];
void init() {
    scanf("%d %d", &N, &M);
    int a, b;
    int bu = 1;
    memset(head, 0, sizeof(head));
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        if (a < 0) {
            ls[i][0] = -a;
            re[i][0] = true;
        }
        else {
            ls[i][0] = a;
            re[i][0] = false;
        }
        if (b < 0) {
            ls[i][1] = -b;
            re[i][1] = true;
        }
        else {
            ls[i][1] = b;
            re[i][1] = false;
        }
        id[bu] = i;
        next[bu] = head[ls[i][0]];
        head[ls[i][0]] = bu++;
        
        id[bu] = i;
        next[bu] = head[ls[i][1]];
        head[ls[i][1]] = bu++;
    }
}
int usf[203];
bool ud[53];
int X;
bool TP;
void FD() {
    int nb[53][2] = {0};
    for (int i = 0; i < M; i++) {
        if (usf[i] == 2) {
            if (ud[ ls[i][0] ] || ud[ ls[i][1] ])
                continue;
            nb[ ls[i][0] ][ re[i][0] ]++;
            nb[ ls[i][1] ][ re[i][1] ]++;
        }
        else if (usf[i] == 1) {
            if (!ud[ ls[i][0] ])
                nb[ ls[i][0] ][ re[i][0] ]++;
            if (!ud[ ls[i][1] ])
                nb[ ls[i][1] ][ re[i][1] ]++;
        }
    }
    int ct = 0;
    for (int i = 1; i <= N; i++) {
        if (ud[i])
            continue;
        if (nb[i][0] + nb[i][1] >= ct) {
            ct = nb[i][0] + nb[i][1];
            X = i;
        }
    }
    if (nb[X][0] < nb[X][1])
        TP = false;
    else
        TP = true;
} 
int ans;
void DFS(int dp, int fnb) {
    if (dp > N) {
        ans = max(ans, M - fnb);
        return;
    }
    if (M - fnb < ans)
        return;
    FD();
    int u = X;
    bool tptp = TP;
    ud[u] = true;
    int ccc = 0;
    for (int j = head[u]; j != 0; j = next[j]) {
        int i = id[j];
        if (ls[i][0] == u && re[i][0] == tptp) 
            usf[i]--;
        if (ls[i][1] == u && re[i][1] == tptp) 
            usf[i]--;
        if (usf[i] == 0)
            ccc++;
    }
    DFS(dp+1, fnb+ccc);
    for (int j = head[u]; j != 0; j = next[j]) {
        int i = id[j];
        if (ls[i][0] == u && re[i][0] == tptp)
            usf[i]++;
        if (ls[i][1] == u && re[i][1] == tptp)
            usf[i]++;
    }
    
    ccc = 0;
    tptp = !tptp;
    for (int j = head[u]; j != 0; j = next[j]) {
        int i = id[j];
        if (ls[i][0] == u && re[i][0] == tptp)
            usf[i]--;
        if (ls[i][1] == u && re[i][1] == tptp)
            usf[i]--;
        if (usf[i] == 0)
            ccc++; 
    }
    DFS(dp+1, fnb+ccc);
    for (int j = head[u]; j != 0; j = next[j]) {
        int i = id[j];
        if (ls[i][0] == u && re[i][0] == tptp)
            usf[i]++;
        if (ls[i][1] == u && re[i][1] == tptp)
            usf[i]++;
    }
    ud[u] = false;
}
void work() {
    init();
    for (int i = 0; i < M; i++)
        usf[i] = 2;
    memset(ud, 0, sizeof(ud));
    ans = 0;
    DFS(1, 0);
    printf("%d\n", ans);
}
int main() {
    freopen("max2sat.in", "r", stdin);
    freopen("max2sat.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--) {
        work();
    }
    return 0;
}
//UBWH