//最短路//dijkstravoid dijkstra() {    memset(vis,0,sizeof(vis));    for(int i = 1;i <= n;i++) {        d[i] = -1;    }    d[n] = 1;    for(int k = 1;k <= n;k++) {        double maxv = -1; int x = n;        for(int i = 1;i <= n;i++) if(!vis[i] && d[i] > maxv) {            maxv = d[x = i];        }        vis[x] = true;        for(int i = 1;i <= n;i++) if(!vis[i] && p[x][i] >= 0) {            if(d[i] == -1) d[i] = d[x] * p[x][i];            else d[i] = max(d[i],d[x] * p[x][i]);        }    }}//dijkstra + heapvoid dijkstra(int *v) {    memset(vis,0,sizeof(vis));    for(int i = 1;i <= n;i++) d[i] = INF;    d[1] = 0;    priority_queue<Node> q;    q.push(Node(d[1],1));    while(!q.empty()) {        Node now = q.top(); q.pop();        int x = now.b;        if(vis[x]) continue;        vis[x] = true;        for(int i = first[x];i != 0;i = nxt[i]) {            if(d[v[i]] > d[x] + w[i]) {                d[v[i]] = d[x] + w[i];                q.push(Node(d[v[i]],v[i]));            }        }    }}//bellman-fordvoid bellman_ford() {    for(int i = 0;i < M;i++) d[i] = INF;    d[0] = 0;    for(int i = 0;i < M;i++) {        for(int j = 0;j < M;j++) {            for(int k = 0;k < M;k++) if(dist[j][k] < INF) {                if(d[j] < INF) {                    d[k] = min(d[k],d[j] + dist[j][k]);                }            }        }    }    printf("%.2f\n",d[M - 1]);}//SPFAvoid spfa(int *v,int *d) {    memset(vis,0,sizeof(vis));    for(int i = 1;i <= N;i++) d[i] = INF;    d[X] = 0;    queue<int> q;    q.push(X);    while(!q.empty()) {        int u = q.front(); q.pop();        vis[u] = false;        for(int i = first[u];i != 0;i = nxt[i]) {            if(d[v[i]] > d[u] + w[i]) {                d[v[i]] = d[u] + w[i];                if(!vis[v[i]]) {                    vis[v[i]] = true;                    q.push(v[i]);                }            }        }    }}//欧拉路和欧拉回路//寻找欧拉路并且输出路径void dfs(int now) {    for(int i = 0;i < e[now].size();i++) {        if(e[now][i].vis == 0) {            e[now][i].vis = 1;            dfs(e[now][i].v);            ans.push(e[now][i].str);        }    }}//网络流//标号法//Ford-Fulkersonvoid solve() {    memset(flow,0,sizeof(flow));    alpha[s] = INF;    while(1) {        //初始化标号        for(int i = 1;i <= t;i++) pre[i] = -2;        pre[s] = -1;        //初始化队列，源点入列        qs = 0; qe = 1;        q[qs] = s;        //标号过程        while(qs < qe && pre[t] == -2) {    //终点没有被标号并且队列非空            int v = q[qs]; qs++;            //printf("now v is %d\n",v);            for(int i = 1;i <= t;i++) {                //如果目标点没有被标号并且还有残余流量                if(pre[i] == -2 && dist[v][i] - flow[v][i] != 0) {                    pre[i] = v;                    alpha[i] = min(alpha[v],dist[v][i] - flow[v][i]);                    q[qe++] = i;                }            }        }        //没有找到到汇点的增广路，退出        if(pre[t] == -2) {            break;        }        //逆向更新        int aval = alpha[t];        for(int i = t;pre[i] != -1;i = pre[i]) {            flow[pre[i]][i] += aval;            flow[i][pre[i]] = -flow[pre[i]][i];        }    }    //统计流量    int ans = 0;    for(int i = 1;i <= n;i++) {        ans += flow[i][t];    }    printf("%d\n",ans);}//dinicbool bfs() {    qs = qe = 0;    q[qe++] = s;    memset(level,0,sizeof(level));    level[s] = 1;    while(qs < qe) {        int v = q[qs++];        if(v == t) break;        for(int i = s;i <= t;i++) if(cap[v][i] && !level[i]) {            level[i] = level[v] + 1;            q[qe++] = i;        }    }    return level[t];} int dfs(int now,int alpha) {    int sum = 0;    if(now == t) return alpha;    for(int i = s;i <= t;i++) {        if(level[i] == level[now] + 1 && alpha && cap[now][i]) {            int ret = dfs(i,min(alpha,cap[now][i]));            cap[now][i] -= ret;            cap[i][now] += ret;            alpha -= ret;            sum += ret;        }    }    return sum;} void dinic() {    int ans = 0;    while(bfs()) ans += dfs(s,INT_MAX);    printf("%d\n",ans);}//混合图欧拉回路的判断//先把所有的边看成是有向边，判断所有的点入度和出度之差是否是偶数，如果有奇数出现那么就不是欧拉回路。//然后去掉图中所有的有向边，建立虚拟的源点和汇点，如果剩下的点中有入度大于出度的，就建立到汇点的边，容量为入度出度之差/2，如果有出度大于入读的，就建立到源点的边，容量同样为入度和出度之差的一半，做一遍最大流，流量和要调换的边的数量相等。//满流的边需要调换using namespace std; typedef long long LL;const int maxn = 205;const int INF = INT_MAX / 3; struct Edge {    int u,v,cap;    Edge(int u,int v,int cap):u(u),v(v),cap(cap) {}}; int n,m,incnt[maxn],outcnt[maxn];int deg[maxn],s,t;vector<Edge> edges;vector<int> e[maxn]; void adde(int u,int v,int w) {    int m = edges.size();    edges.push_back(Edge(u,v,w));    edges.push_back(Edge(v,u,0));    e[u].push_back(m);    e[v].push_back(m ^ 1);} int level[maxn],q[maxn * 2],qs,qe;bool bfs() {    //建立层次网络    memset(level,0,sizeof(level));    level[s] = 1;    qs = qe = 0;    q[qe++] = s;    while(qs < qe) {        int now = q[qs++],nm = e[now].size();        if(now == t) break;        for(int i = 0;i < nm;i++) {            Edge &ne = edges[e[now][i]];            if(ne.cap && level[ne.v] == 0) {                level[ne.v] = level[now] + 1;                q[qe++] = ne.v;            }        }    }    return level[t];} int dfs(int now,int alpha) {    if(now == t) return alpha;    int sum = 0,nm = e[now].size();    for(int i = 0;i < nm;i++) {        Edge &ne = edges[e[now][i]];        if(level[now] + 1 == level[ne.v] && ne.cap && alpha) {            int ret = dfs(ne.v,min(alpha,ne.cap));            ne.cap -= ret; edges[e[now][i] ^ 1].cap += ret;            sum += ret; alpha -= ret;        }    }    if(sum == 0) level[now] = -1;    return sum;} void dinic() {    while(bfs()) dfs(s,INF);} bool solve() {    s = 0; t = n + 1;    //判断入度出度之差是否为偶数    for(int i = 1;i <= n;i++) {        deg[i] = incnt[i] - outcnt[i];        if(deg[i] & 1) return false;    }    //建立容量网络    for(int i = 1;i <= n;i++) {        //如果入度小于出度,建立从起点到这个点的边，容量为deg/2        if(deg[i] < 0) adde(s,i,-deg[i] / 2);        //如果出度大于入读，建立从当前点到汇点的边，容量同样为deg/2        if(deg[i] > 0) adde(i,t,deg[i] / 2);    }    //计算最大流    dinic();    //判断从源点出发的所有边是否满流    int m = e[s].size();    for(int i = 0;i < m;i++) {        if(edges[e[s][i]].cap != 0) return false;    }    return true;} int main() {    int T; scanf("%d",&T);    while(T--) {        scanf("%d%d",&n,&m);        edges.clear();        for(int i = 0;i <= n + 1;i++) e[i].clear();        memset(incnt,0,sizeof(incnt));        memset(outcnt,0,sizeof(outcnt));        for(int i = 1;i <= m;i++) {            int u,v,c; scanf("%d%d%d",&u,&v,&c);            //先将无向边全部作为有向边处理            incnt[v]++; outcnt[u]++;            //无向边存起来            if(c == 0) adde(u,v,1);        }        if(solve()) puts("possible");        else puts("impossible");    }    return 0;}//求最小割是否唯一//判断方法是先做一遍最大流求最小割，然后从源点和汇点分别遍历所有能够到达的点，看是否覆盖了所有的点，如果覆盖了所有的点，那就是唯一的，否则就是不唯一的。void solve() {    //先做一遍最大流       while(bfs()) dfs(s,INF);    //分别从起点和终点做一遍bfs    memset(vis,0,sizeof(vis));    qs = qe = 0;    q[qe++] = s;    vis[s] = true;    while(qs < qe) {        int now = q[qs++];        for(int i = first[now];~i;i = nxt[i]) {            if(cap[i] && !vis[v[i]]) {                vis[v[i]] = true; q[qe++] = v[i];            }        }    }    qs = qe = 0;    q[qe++] = t;    vis[t] = true;    while(qs < qe) {        int now = q[qs++];        for(int i = first[now];~i;i = nxt[i]) {            if(cap[i ^ 1] && !vis[v[i]]) {                vis[v[i]] = true; q[qe++] = v[i];            }        }    }    for(int i = 1;i <= n;i++) {        if(!vis[i]) {            puts("AMBIGUOUS");            return;        }    }    puts("UNIQUE");}//带容量限制的无源点和汇点的网络流//建立虚拟的源点和汇点，因为忽略掉了容量下界之后会导致流量不平衡，所以对于每个u，v，u多出来的流量流到汇点，v不够的流量从源点补流typedef long long LL;const int maxn = 205;const int maxm = maxn * maxn;const int INF = INT_MAX / 3;int cap[maxn][maxn],flow[maxn][maxn],low[maxm];int q[maxn],alpha[maxn],pre[maxn];int uu[maxm],vv[maxm];int n,m,s,t,qs,qe;void solve() {    memset(flow,0,sizeof(flow));    while(1) {        qs = qe = 0;        for(int i = s;i <= t;i++) pre[i] = -2;        pre[s] = -1; alpha[s] = INF;        q[qe++] = s;        while(qs < qe) {            int now = q[qs++];            for(int i = s;i <= t;i++) {                if(cap[now][i] - flow[now][i] != 0 && pre[i] == -2) {                    q[qe++] = i;                    pre[i] = now;                     alpha[i] = min(alpha[now],cap[now][i] - flow[now][i]);                }            }        }        if(pre[t] == -2) break;        for(int i = t;pre[i] != -1;i = pre[i]) {            flow[pre[i]][i] += alpha[t];            flow[i][pre[i]] -= alpha[t];        }    }    bool ok = true;    for(int i = s + 1;i <= t;i++) {        if(cap[s][i] - flow[s][i]) ok = false;    }    for(int i = s;i < t;i++) if(cap[i][t] - flow[i][t]) ok = false;    if(!ok) puts("NO");    else {        puts("YES");        for(int i = 0;i < m;i++) {            printf("%d\n",flow[uu[i]][vv[i]] + low[i]);        }    }}int main() {    scanf("%d%d",&n,&m);    s = 0; t = n + 1;    memset(cap,0,sizeof(cap));    for(int i = 0;i < m;i++) {        int u,v,l,c; scanf("%d%d%d%d",&u,&v,&l,&c);        low[i] = l;        cap[u][v] += c - l;        cap[s][v] += l;        cap[u][t] += l;        uu[i] = u; vv[i] = v;    }    solve();    return 0;}//二分图最大匹配int dfs(int now) {    for(int i = 1;i <= cnty;i++) if(g[now][i] && !vis[i]) {        vis[i] = true;        if(!by[i] || dfs(by[i])) {            bx[now] = i; by[i] = now;            return 1;        }    }    return 0;} int solve() {    int ret = 0;    memset(bx,0,sizeof(bx));    memset(by,0,sizeof(by));    for(int i = 1;i <= cntx;i++) if(!bx[i]) {        memset(vis,0,sizeof(vis));        ret += dfs(i);    }    return ret;}//最小点权覆盖->最小割+拆点//求最大独立集 最大独立点集 = 点数 - 最大匹配数注意//最小点覆盖 == 最大匹配//最小路径覆盖 = 顶点数 - 最大匹配