#include <bits/stdc++.h>
//#define int long long
//#define mod 1000000007
using namespace std;

int n,m,head[300010],cnt=1,ru[300010],tmp,cz[600010],tot;
int huan[300010],ruh[300010],head2[300010],cnt2,tmp2,zhan[300010],ztop;
bool vis[300010],vis2[300010],vis3[300010],vis4[500010];
vector<int> h[300010],d[300010];
set<int> hu[300010];
struct edge
{
	int next,to;
}a[500010],a2[500010];
void ad(int u,int v)
{
	a[++cnt].to=v;a[cnt].next=head[u];head[u]=cnt;ru[v]++;
	a[++cnt].to=u;a[cnt].next=head[v];head[v]=cnt;ru[u]++;
}
void ad2(int u,int v)
{
	a2[++cnt2].to=v;a2[cnt2].next=head2[u];head2[u]=cnt2;ruh[v]++;
	a2[++cnt2].to=u;a2[cnt2].next=head2[v];head2[v]=cnt2;ruh[u]++;
}
void dfs(int x,int fa)
{
	if(vis2[x])
	{
		int now=ztop;tmp2++;
		h[tmp2].push_back(x);huan[tmp2]++;
		for(auto j:d[x]) ad(tmp2,j);
		d[x].push_back(tmp2);
		while(zhan[now]!=x)
		{
			h[tmp2].push_back(zhan[now]);
			for(auto j:d[zhan[now]]) ad(tmp2,j);
			if(!d[zhan[now]].empty()) hu[tmp2].insert(zhan[now]);
			d[zhan[now]].push_back(tmp2);
			now--;huan[tmp2]++;
		}
		return;
	}
	vis2[x]=1;zhan[++ztop]=x;
	for(int i=head[x];i;i=a[i].next)
	{
		int v=a[i].to;
		if(vis[v]||v==fa||vis4[i]||vis4[i^1]) continue;
		dfs(v,x);vis4[i]=1;ztop--;
	}
}
signed main()
{
	cin>>n>>m;tmp=n;
	for(int i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;ad(u,v);
	}
	set<int> echo;//cout<<"0 ";
	for(int i=1;i<=n;i++)
	{
		if(ru[i]%2) echo.insert(i);
	}
	while(!echo.empty())
	{
		set<int>::iterator it=echo.begin();
		int now=*it;echo.erase(now);
		cz[++tot]=now;vis[now]=1;tmp--;
		for(int i=head[now];i;i=a[i].next)
		{
			int v=a[i].to;
			if(vis[v]) continue;
			ru[v]--;
			if(ru[v]%2) echo.insert(v);
			else echo.erase(v);
			if(!ru[v]) tmp--;
		}
	}
	queue<int> q;
	if(tmp==0) goto Marshall_Maximizer;
	cz[++tot]=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]&&!vis2[i]) dfs(i,0);
	}
	for(int i=1;i<=tmp2;i++)
	{
		if(ruh[i]==1||!ruh[i]) q.push(i);
	}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		int k,fl=0,fl2=0;
		if(ruh[u]) k=*hu[u].begin();
		else k=h[u][0];
		cout<<"!"<<k<<'\n';
		for(auto j:h[u])
		{
			if(j==k)
			{
				fl2=fl;continue;
			}
			cz[++tot]=j+fl*n;
			fl^=1;
		}
		int lst,nxt;
		for(int i=0;i<h[u].size();i++)
		{
			if(h[u][i]!=k) continue;
			if(i==0) lst=h[u][h[u].size()-1];
			else lst=h[u][i-1];
			if(i==h[u].size()-1) nxt=h[u][0];
			else nxt=h[u][i+1];
			break;
		}
		if(huan[u]%2)
		{
			if(fl2)
			{
				cz[++tot]=lst+n;cz[++tot]=nxt;
			}
			else
			{
				cz[++tot]=lst;cz[++tot]=nxt+n;
			}
		}
		else
		{
			if(fl2)
			{
				cz[++tot]=lst+n;cz[++tot]=nxt+n;
			}
			else
			{
				cz[++tot]=lst;cz[++tot]=nxt;
			}
		}
		vis3[u]=1;
		if(!ruh[u]) cz[++tot]=k;
		for(int i=head2[u];i;i=a2[i].next)
		{
			int v=a2[i].to;
			if(vis3[v]) continue;
			ru[v]--;
			if(ru[v]==1) q.push(v);
			if(ru[v]) hu[v].erase(k);
		}
	}
	Marshall_Maximizer:
	cout<<tot<<'\n';
	for(int i=1;i<=tot;i++)
	{
		if(cz[i]==0) cout<<"2\n";
		else cout<<"1 "<<cz[i]<<'\n';
	}
	return 0;
}