原來混合圖歐拉回路用的是網(wǎng)絡流。 
　　把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數(shù)，那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數(shù)為偶數(shù)，存在奇數(shù)度點必不能有歐拉回路。 
　　好了，現(xiàn)在每個點入度和出度之差均為偶數(shù)。那么將這個偶數(shù)除以2，得x。也就是說，對于每一個點，只要將x條邊改變方向（入>出就是變?nèi)耄?gt;入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那么很明顯，該圖就存在歐拉回路。 
　　現(xiàn)在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構(gòu)造網(wǎng)絡流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網(wǎng)絡構(gòu)建成什么樣，邊長容量上限1。另新建s和t。對于入 > 出的點u，連接邊(u, t)、容量為x，對于出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？察看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。 
　　由于是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那么，沒和s、t連接的點怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個既沒和s也沒和t連接的點，自然早在開始就已經(jīng)滿足入 = 出了。那么在網(wǎng)絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之后，自然仍保持平衡。 
所以，就這樣，混合圖歐拉回路問題，解了。

最大流ISAP
#include<iostream>
#define maxn 300
const int inf=1000000000;
using namespace std;
struct edge
{
    int u,v,next,f,pre;
}e[10000];
int num;
int head[maxn],rhead[maxn];
int d[maxn];
int numb[maxn];
int start[maxn];
int n,m;
int p[maxn];
int in[maxn],out[maxn];
int source,sink;
void Init()
{
    memset(head,-1,sizeof(head));
    memset(rhead,-1,sizeof(rhead));
    memset(p,-1,sizeof(p));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    num=0;
    return ;
}
void BFS()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        d[i]=n;
        numb[i]=0;
    }
    int Q[maxn],head(0),tail(0);
    d[sink]=0;
    numb[0]=1;
    Q[++tail]=sink;
    while(head<tail)
    {
        i=Q[++head];
        for(j=rhead[i];j!=-1;j=e[j].pre)
        {
            if(e[j].f==0||d[e[j].u]<n)
                continue;
            d[e[j].u]=d[i]+1;
            numb[d[e[j].u]]++;
            Q[++tail]=e[j].u;
        }
    }
    return ;
}
int Augment()
{
    int i;
    int tmp=inf;
    for(i=p[sink];i!=-1;i=p[e[i].u])
    {
        if(tmp>e[i].f)
            tmp=e[i].f;
    }
    for(i=p[sink];i!=-1;i=p[e[i].u])
    {
        e[i].f-=tmp;
        e[i^1].f+=tmp;
    }
    return tmp;
}
int Retreat(int &i)
{
    int tmp,j,mind(n-1);
    for(j=head[i];j!=-1;j=e[j].next)
    {
        if(e[j].f>0&&d[e[j].v]<mind)
            mind=d[e[j].v];
    }
    tmp=d[i];
    d[i]=mind+1;
    numb[tmp]--;
    numb[d[i]]++;
    if(i!=source)
        i=e[p[i]].u;
    return numb[tmp];
}
int maxflow()
{
    int flow(0),i,j;
    BFS();
    for(i=0;i<n;i++)
        start[i]=head[i];
    i=source;
    while(d[source]<n)
    {
        for(j=start[i];j!=-1;j=e[j].next)
            if(e[j].f>0&&d[i]==d[e[j].v]+1)
                break;
        if(j!=-1)
        {
            start[i]=j;
            p[e[j].v]=j;
            i=e[j].v;
            if(i==sink)
            {
                flow+=Augment();
                i=source;
            }
        }
        else
        {
            start[i]=head[i];
            if(Retreat(i)==0)
                break;
        }
    }
    return flow;
}
void addedge(int a,int b,int c)
{
    e[num].next=head[a];
    head[a]=num;
    e[num].pre=rhead[b];
    rhead[b]=num;
    e[num].f=c;
    e[num].u=a;
    e[num++].v=b;
    e[num].next=head[b];
    head[b]=num;
    e[num].pre=rhead[a];
    rhead[a]=num;
    e[num].u=b;
    e[num].v=a;
    e[num++].f=0;
    return ;
}
int main()
{
    int i;
    int a,b,c;
    int cas;
    int nn;
    scanf("%d",&cas);
    while(cas--)
    {
        bool flag=0;
        scanf("%d%d",&nn,&m);
        n=nn+2;
        source=0;
        sink=nn+1;
        Init();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(a==b)
                continue;
            if(c==0)
            {
                addedge(a,b,1);
            }
            in[b]++;
            out[a]++;
        }
        for(i=1;i<=n;i++)
        {
            if(abs(in[i]-out[i])%2==1)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
            printf("impossible\n");
        else
        {
            int sum=0;
            for(i=1;i<=n;i++)
            {
                int tmp=(out[i]-in[i])>>1;
                if(tmp<0)
                    addedge(i,sink,-tmp);
                else if(tmp>0)
                {
                    addedge(source,i,tmp);
                    sum+=tmp;
                }
            }
            int flow=0;
            flow=maxflow();
            if(flow!=sum)
                flag=1;
            if(flag==1)
                printf("impossible\n");
            else
                printf("possible\n");
        }
    }
    system("pause");
    return 0;
}