# 2. 题解

emmm…

emmm…

1. 对于出度大于入度的，从源点连一条容量为 $c\div 2$的边。
2. 对于入度大于出度的，从它连一条容量为 $c\div 2$的边到汇点。
3. 对于一条随机成 $a->b$的无向边，从 $a$连一条容量为 1 的边到 $b$。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
#include <algorithm>
#include <cmath>

#define NS (205)
#define MS (3005)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct graph
{
int head[NS], nxt[MS], to[MS], f[MS], sz;
graph() {init();}
void push(int a, int b, int c)
{
nxt[sz] = head[a], to[sz] = b, f[sz] = c, head[a] = sz++;
}
void add(int a, int b, int c)
{
push(a, b, c), push(b, a, 0);
}
} g;

int Ca, n, m, T, in[NS], ou[NS], cur[MS], rem, dep[NS];

queue<int> que;

bool bfs()
{
memset(dep, 0, sizeof(dep)), dep[0] = 1, que.push(0);
while (!que.empty())
{
int F = que.front(); que.pop();
for (int i = g.head[F]; ~i; i = g.nxt[i])
if (g.f[i] && !dep[g[i]])
dep[g[i]] = dep[F] + 1, que.push(g[i]);
}
return (dep[T] != 0);
}

int dfs(int a, int f)
{
if (a == T) return f;
for (int& i = cur[a]; ~i; i = g.nxt[i])
if (dep[g[i]] == dep[a] + 1 && g.f[i])
{
int tmp = dfs(g[i], min(f, g.f[i]));
if (tmp)
{
g.f[i] -= tmp, g.f[i ^ 1] += tmp;
return tmp;
}
}
return 0;
}

int main(int argc, char const* argv[])
{
IN(Ca);
while (Ca--)
{
IN(n), IN(m), srand(n * m), T = n + 1;
for (int i = 1, a, b, c; i <= m; i += 1)
if (IN(a), IN(b), IN(c), c == 1) ou[a]++, in[b]++;
else if (rand() & 1) ou[a]++, in[b]++, g.add(a, b, 1);
else ou[b]++, in[a]++, g.add(b, a, 1);
for (int i = 1; i <= n; i += 1)
{
if (abs(in[i] - ou[i]) & 1) {puts("impossible"); goto end;}
if (in[i] > ou[i]) g.add(i, T, (in[i] - ou[i]) >> 1);
else g.add(0, i, (ou[i] - in[i]) >> 1), rem += (ou[i] - in[i]) >> 1;
}
while (bfs())
{
int tmp;
while (tmp = dfs(0, 1e8)) rem -= tmp;
}
if (!rem) puts("possible");
else puts("impossible");
end : g.init(), rem = 0;
memset(in, 0, sizeof(in)), memset(ou, 0, sizeof(ou));
}
return 0;
}