Description

 Perfectxx给LZH出了一道题，要LZH构造出一个尽可能大的四色图。所谓的四色图指的是由n个点m条边组成的无向图。其中，每个点要么是红色，要么是蓝色，每条边要么是黑色，要么是白色。

黑边能连接两个红点，或是一个红点与一个蓝点。而白边只能连接红点与蓝点。

LZH构造出了一个图，但是委托给Murphyc,让他去打印的时候，Murphyc用了黑白打印机。现在分不清楚顶点的颜色是红还是蓝。

现在你需要帮Perfectxx检查一下，LZH构造出的图有没有可能是四色图。

Input

第一行输入n和m，表示点的数量和边的数量 (1<=n,m<=2e5)

接下来的m行，每行三个输入 w u v 表示图中有一条从u到v的无向边，w=1时表示

这条边是黑边，w=0是表示这条边是白边。

Output

仅输出一行字符串，其中”Maybe”表示原图有可能是四色图,”Impossible”表示原图一定不是四色图。（输出中没有引号）

Sample Input

4 4 0 1 2 0 2 3 0 3 4 0 4 1 3 3 0 1 2 0 2 3 0 3 1

Sample Output

Maybe Impossible

HINT

题解：

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int ins[N],dfn[N],low[N],cnt,sta[N];
int top,v,u;
int Next[N],head[N],to[N];
int tot;
int scc[N];
int scccnt;
void make_list(int u,int v){
	Next[++tot]=head[u],head[u]=tot,to[tot]=v;
}
void tarjan(int x){
    ins[x]=dfn[x]=low[x]=++cnt,sta[top++]=x;
    for(int p=head[x],v=to[p];p;p=Next[p],v=to[p])
        if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
        else if(ins[v])low[x]=min(low[x],dfn[v]);
    if(low[x]==dfn[x]){
        scc[x]=++scccnt,ins[x]=0;
        while((u=sta[--top])!=x)ins[u]=0,scc[u]=scccnt;
    }
}
int main(){
	int n,m,w,u,v;
	freopen("data5.in","r",stdin);
	freopen("data5.out","w",stdout);	
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&w,&u,&v);
		if(!w){
			make_list(u,v+n);
			make_list(v,u+n);
			make_list(u+n,v);
			make_list(v+n,u);
		}
		else{
			make_list(u+n,v);
			make_list(v+n,u);
		}
	}
	
	for(int i=1;i<=2*n;i++){
		if(!dfn[i])tarjan(i);
	}
	bool ok=1;
	for(int i=1;i<=n;i++){
		ok&=(scc[i]!=scc[i+n]);
	}
	if(ok)puts("Maybe");
	else puts("Impossible");
	return 0; 
}