Pagini recente » Cod sursa (job #1949170) | Cod sursa (job #2968394) | Cod sursa (job #1094938) | Cod sursa (job #2805893) | Cod sursa (job #987450)
Cod sursa(job #987450)
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define In "johnie.in"
#define Out "johnie.out"
#define Nmax 50004
#define pb push_back
#define Lim 1000000
#define Next ((++pos==Lim )? f.read(Buffer,Lim) ,pos = 0: 0)
using namespace std;
vector< int >Graph[Nmax],a;
vector< vector < int > > sol;
int n, m, degree[Nmax], pos;
ifstream f(In);
char Buffer[Lim];
inline void Read(int &x)
{
x = 0;
for(;Buffer[pos] < '0' || Buffer[pos] > '9'; Next);
for(;Buffer[pos] >= '0' && Buffer[pos] <= '9'; Next)
x = x*10+Buffer[pos]-'0';
}
inline void Read()
{
f.read(Buffer,Lim);
freopen(Out,"w",stdout);
Read(n);Read(m);
int i,x,y;
for(i = 1 ;i <= m ; ++i)
{
Read(x);Read(y);
Graph[x].pb(y);
Graph[y].pb(x);
++degree[x];
++degree[y];
}
}
inline void Dfs(int node)
{
stack< int >St;
St.push(node);
int y;
while(!St.empty())
{
node = St.top();
if(!Graph[node].size())
{
St.pop();
if(node==0)
{
sol.pb(a);
a.clear();
}
else
a.pb(node);
}
else
{
y = Graph[node].back();
St.push(y);
Graph[node].pop_back();
Graph[y].erase(find(Graph[y].begin(),Graph[y].end(),node));
}
}
}
inline void Solve()
{
for(int i = 1;i <= n; ++i)
if(degree[i]&1)
{
Graph[0].pb(i);
Graph[i].pb(0);
}
Dfs(0);
}
inline void Write()
{
int k = sol.size();
printf("%d\n",k-1);
vector<int >::iterator it;
for(int i = 1;i < k; ++i)
{
printf("%d ",sol[i].size());
for(it = sol[i].begin();it!=sol[i].end();++it)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
Read();
Solve();
Write();
return 0;
}