#include <iostream>
#include <bitset>
#include <climits>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class disjoint_set{
vector < int > parent;
vector < int > sz;
public:
disjoint_set ( int n ){
parent.resize( n + 1 );
for( int i = 1; i <= n; ++i )
parent[i] = i;
sz.resize( n + 1 );
fill(sz.begin(), sz.end(), 1);
}
int Find( int x );
void Union( int x, int y );
};
int disjoint_set::Find( int x ){
int aux, root = x;
while( parent[root] != root ) root = parent[root];
while( parent[x] != x ){
aux = parent[x];
parent[x] = root;
x = aux;
}
return root;
}
void disjoint_set::Union(int x, int y){
int root_x = Find(x);
int root_y = Find(y);
if( sz[root_x] >= sz[root_y] ){
sz[root_x] += sz[root_y];
parent[root_y] = root_x;
}
else{
sz[root_y] += sz[root_x];
parent[root_x] = root_y;
}
}
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
class graph{
protected:
const int INF = INT_MAX;
vector< vector < int > > Ad;
vector< vector < int > > EdgeValue;
const int nodes;
int edges = 0;
private:
void DFSr( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp );
void DFSdiameter( int nod, int parent, int lg, int& lgmax, int& last );
void TopoDFS( int nod, vector < bool > & vis, stack < int > & topo );
void BridgesDFS( int nod, int parent, vector < bool >& vis, vector < int >& desc, vector < int >& low, vector < pair < int, int > >& bridges );
void BiconnectedDFS( int nod, int parent, vector < bool >& vis, stack < int >& topo, vector < int >& desc, vector < int >& low, vector < vector < int > >& bcc );
bool BFSflow( int source, int sync, const vector < vector < int > > & AdRes, int** cap, int** flow, int* parent );
void EulerianCircuitSearch( int nod, vector < vector < pair < int, int > > >& Edge, vector < bool > & Vis, vector < int >& Sol );
public:
graph( int n):nodes(n){ Ad.resize(nodes+1); EdgeValue.resize(nodes+1); }
graph( int n, int m, vector < vector < int > > & ad ) : nodes(n), edges(m), Ad(ad) {}
graph( int n, int m, vector < vector < int > > & ad, vector < vector < int > > & values ) : nodes(n), edges(m){
Ad.resize(nodes+1);
EdgeValue.resize(nodes+1);
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < ad[i].size(); ++j){
Ad[i].push_back(ad[i][j]);
EdgeValue[i].push_back(values[i][j]);
}
}
int getNodes(){ return nodes; }
void addEdge(int x, int y, bool oriented, int value );
void DFS( int nod, vector < bool >& vis);
vector < int > BFS( int nod );
int ConnectedComponents();
pair < int, vector < pair < int , int > > > Kruskal();
vector < int > Dijkstra( int source );
pair < bool, vector < int > > BellmanFord( int source );
stack < int > TopoSort();
vector < vector < int > > StronglyConnectedComponents();
vector < pair < int, int > > Bridges();
vector < vector < int > > BiconnectedComponents();
int** RoyFloyd();
int Diameter();
int MaxFlow( int source, int sync );
vector < int > EulerianCircuit( int source );
int MinimumCostHamiltonianCircuit();
};
class bipartiteGraph : protected graph{
int leftNodes, rightNodes;
public:
bipartiteGraph(int lf, int rg, int m, vector < vector < int > >& ad):graph(lf+rg, m, ad), leftNodes(lf), rightNodes(rg){}
inline bool Match( int nod, vector < int >& matchL, vector < int >& matchR, vector < bool >& vis );
vector < pair < int, int > > MaximumMatching();
};
void graph::addEdge(int x, int y, bool oriented, int value = INT_MAX ){
Ad[x].push_back( y );
if( value != INT_MAX )
EdgeValue[x].push_back(value);
if( oriented == false ) {
Ad[y].push_back(x);
if( value != INT_MAX )
EdgeValue[y].push_back(value);
}
edges++;
}
void graph::DFS( int nod, vector < bool >& vis ){
vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( vis[w] == 0 )DFS(w,vis);
}
}
void graph::DFSr( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp ){
vis[nod] = 1;
comp.push_back( nod );
for( int i = 0; i < ad[nod].size(); ++i ){
int w = ad[nod][i];
if( vis[w] == 0 )DFSr(w, vis, ad, comp);
}
}
vector < int > graph::BFS( int nod ){
queue < int > Q;
vector < int > dist(nodes+1, 0);
Q.push(nod);
int x;
while( !Q.empty() ){
x = Q.front();
Q.pop();
for( int i = 0; i < Ad[x].size(); ++i ){
int w = Ad[x][i];
if( dist[w] == 0 && w != x && w != nod ){
dist[w] = dist[x] + 1;
Q.push(w);
}
}
}
for( int i = 1; i <= nodes; ++i )
if( !(dist[i] != 0 || i == nod) )dist[i] = -1;
return dist;
}
int graph::ConnectedComponents(){
int nr = 0;
vector < bool > vis(nodes+1, 0);
for( int i = 1; i <= nodes; ++i )
if( vis[i] == 0 ){
DFS(i,vis);
nr++;
}
return nr;
}
pair < int, vector < pair < int , int > > > graph::Kruskal(){
struct edge{
int x, y, v;
bool operator < ( const edge & E ) {
return v < E.v;
}
};
vector < edge > E;
disjoint_set ds(nodes);
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < Ad[i].size(); ++j ){
E.push_back({i,Ad[i][j],EdgeValue[i][j]});
}
sort( E.begin(), E.end() );
vector < pair < int , int > > Sol;
int TotalValue = 0, edges_nr = 0;
for( int i = 0; i < edges && edges_nr < nodes; ++i ){
int root_x = ds.Find( E[i].x );
int root_y = ds.Find( E[i].y );
if( root_x != root_y ){
edges_nr++;
Sol.push_back( {E[i].x, E[i].y} );
TotalValue += E[i].v;
ds.Union( root_x, root_y );
}
}
return make_pair(TotalValue, Sol);
}
vector < int > graph::Dijkstra(int source){
priority_queue< pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > > > H;
vector < int > dist(nodes+1,INF);
vector < bool > vis(nodes+1, 0);
dist[source] = 0;
H.push( {0,source} );
int nod;
while( !H.empty() ){
nod = H.top().second;
H.pop();
if( vis[nod] ) continue;
else vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
int dw = EdgeValue[nod][i];
if( dist[w] > dist[nod] + dw ){
dist[w] = dist[nod] + dw;
H.push( { dist[w], w } );
}
}
}
for( int i = 2; i <= nodes; ++i )
if( dist[i] == INF ) dist[i] = 0;
return dist;
}
pair < bool, vector < int > > graph::BellmanFord( int source ){
vector < int > dist(nodes+1, INF);
vector < int > visCount(nodes+1, 0);
vector < bool > inQ( nodes+1, 0);
queue < int > Q;
dist[source] = 0;
Q.push( source );
int nod;
bool negativeCicle = false;
while( !Q.empty() && !negativeCicle ){
nod = Q.front();
Q.pop();
inQ[nod] = false;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
int dw = EdgeValue[nod][i];
if( dist[w] > dist[nod] + dw ){
dist[w] = dist[nod] + dw;
//cout << nod << ' ' << w << ' ' << dist[w] << '\n';
if( inQ[w] == false ){
inQ[w] = true;
Q.push( w );
}
visCount[w]++;
if( visCount[w] == nodes ){
negativeCicle = true;
break;
}
}
}
}
return make_pair( negativeCicle, dist );
}
void graph::TopoDFS( int nod, vector < bool > & vis, stack < int > & topo ){
vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( !vis[w] )
TopoDFS( w, vis, topo );
}
topo.push(nod);
}
stack < int > graph :: TopoSort(){
vector < bool > vis(nodes+1, 0);
stack < int > Topo;
for( int i = 1; i <= nodes; ++i )
if( !vis[i] )
TopoDFS( i, vis, Topo );
return Topo;
}
vector < vector < int > > graph::StronglyConnectedComponents(){
vector < vector < int > > Ad_r;
Ad_r.resize(nodes+1);
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < Ad[i].size(); ++j)
Ad_r[Ad[i][j]].push_back(i);
stack < int > Topo;
vector < bool > vis(nodes+1, 0);
for( int i = 1; i <= nodes; ++i )
if( !vis[i] )
TopoDFS( i, vis, Topo );
vector < vector < int > > scc;
fill(vis.begin(), vis.end(), 0);
while( !Topo.empty() ){
if( !vis[Topo.top()] ){
vector < int > comp;
DFSr( Topo.top(), vis, Ad_r, comp);
scc.push_back( comp );
}
Topo.pop();
}
return scc;
}
void graph::BridgesDFS(int nod, int parent, vector <bool>& vis, vector<int>& desc, vector<int>& low, vector<pair<int,int>>& bridges) {
vis[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( !vis[w] ){
desc[w] = 1 + desc[nod];
BridgesDFS( w, nod, vis, desc, low, bridges );
low[nod] = min( low[nod], low[w] );
if( low[w] > desc[nod] && w != parent )
bridges.push_back( {nod, w} );
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
vector < pair < int, int > > graph::Bridges() {
vector < bool > vis(nodes+1, 0 );
vector < int > low(nodes+1 );
vector < int > desc( nodes+1 );
vector < pair < int, int > > bridges;
desc[1] = 1;
BridgesDFS(1, 0, vis, desc, low, bridges );
return bridges;
}
void graph::BiconnectedDFS(int nod, int parent, vector<bool> &vis, stack<int> &st, vector<int> &desc,
vector<int> &low, vector<vector<int>> &bcc) {
vis[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( !vis[w] ){
st.push( w );
desc[w] = 1 + desc[nod];
BiconnectedDFS( w, nod, vis, st, desc, low, bcc );
low[nod] = min( low[nod], low[w] );
if( low[w] >= desc[nod] && w != parent ){
st.push( nod );
vector < int > comp;
while( st.size() && st.top() != w ){
comp.push_back( st.top() );
st.pop();
}
if( st.size() ){
comp.push_back( st.top() );
st.pop();
}
bcc.push_back(comp);
}
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
vector < vector < int > > graph::BiconnectedComponents() {
vector < bool > vis(nodes+1, 0 );
vector < int > low(nodes+1 );
vector < int > desc( nodes+1 );
vector < vector < int > > bcc;
stack < int > st;
desc[1] = 1;
BiconnectedDFS(1, 0, vis, st, desc, low, bcc);
return bcc;
}
int** graph::RoyFloyd(){
int** RF = new int* [nodes+1];
for( int i = 1; i <= nodes; ++i ){
RF[i] = new int [nodes+1];
for( int j = 1; j <= nodes; ++j )
RF[i][j] = INF;
RF[i][i] = 0;
}
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < Ad[i].size(); ++j )
RF[i][Ad[i][j]] = EdgeValue[i][j];
for( int k = 1; k <= nodes; ++k )
for( int i = 1; i <= nodes; ++i )
for( int j = 1; j <= nodes; ++j )
if( RF[i][j] > (1LL * RF[i][k] + RF[k][j]) )
RF[i][j] = RF[i][k] + RF[k][j];
for( int i = 1; i <= nodes; ++i )
for( int j = 1; j <= nodes; ++j )
if( RF[i][j] == INF )
RF[i][j] = 0;
return RF;
}
void graph::DFSdiameter( int nod, int parent, int lg, int& lgmax, int& last ){
if( lg > lgmax ){
lgmax = lg;
last = nod;
}
for( int i = 0; i < Ad[nod].size(); ++i )
if( Ad[nod][i] != parent )
DFSdiameter( Ad[nod][i], nod, lg+1, lgmax, last );
}
int graph::Diameter(){
int lgmax = 0;
int last;
DFSdiameter( 1, 0, 1, lgmax, last );
lgmax = 0;
DFSdiameter( last, 0, 1, lgmax, last );
return lgmax;
}
bool graph::BFSflow(int source, int sync, const vector < vector < int > > & AdRes, int **cap, int **flow, int *parent){
for( int i = 1; i <= nodes; ++i ) parent[i] = 0;
queue < int > Q;
Q.push( source );
int nod;
parent[source] = -1;
while( !Q.empty() ){
nod = Q.front();
Q.pop();
if( nod == sync ) continue;
for( int i = 0; i < AdRes[nod].size(); ++i ){
int w = AdRes[nod][i];
if( !parent[w] && cap[nod][w] - flow[nod][w] > 0 ){
parent[w] = nod;
Q.push( w );
}
}
}
return (parent[sync] != 0);
}
int graph::MaxFlow( int source, int sync ) {
vector < vector < int > > AdRes;
AdRes.resize(nodes+1);
int** cap = new int* [nodes+1];
int** flow = new int* [nodes+1];
for( int i = 1; i <= nodes; ++i ){
cap[i] = new int [nodes+1];
flow[i] = new int [nodes+1];
for( int j = 1; j <= nodes; ++j )
cap[i][j] = flow[i][j] = 0;
}
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < Ad[i].size(); ++j ){
AdRes[i].push_back(Ad[i][j]);
AdRes[Ad[i][j]].push_back(i);
cap[i][Ad[i][j]] = EdgeValue[i][j];
}
int* parent = new int [nodes+1];
int totalFlow = 0;
while( BFSflow(source, sync, AdRes, cap, flow, parent) ){
for( int i = 0; i < AdRes[sync].size(); ++i ){
int w = AdRes[sync][i];
if( parent[w] && cap[w][sync] - flow[w][sync] > 0 ){
parent[sync] = w;
int flowBottleneck = INF;
for( int nod = sync; nod != source; nod = parent[nod] )
flowBottleneck = min( flowBottleneck, cap[parent[nod]][nod] - flow[parent[nod]][nod] );
for( int nod = sync; nod != source; nod = parent[nod] ) {
flow[parent[nod]][nod] += flowBottleneck;
flow[nod][parent[nod]] -= flowBottleneck;
}
totalFlow += flowBottleneck;
}
}
}
for( int i = 1; i <= nodes; ++i ){
delete [] cap[i];
delete [] flow[i];
}
delete [] cap;
delete [] flow;
delete [] parent;
return totalFlow;
}
vector < int > graph::EulerianCircuit( int source ){
vector < pair < int, int > > Edges;
vector < vector < pair < int, int > > > Edge;
Edge.resize(nodes+1);
vector < bool > Vis;
Vis.resize( edges+1 );
int edgeCount = 0;
for( int i = 1; i <= nodes; ++i )
for( int j = 0; j < Ad[i].size(); ++j )
Edges.push_back({min(i,Ad[i][j]),max(i,Ad[i][j])});
sort(Edges.begin(), Edges.end() );
//cout << Edges.size() << '\n';
for( int i = 0; i < Edges.size(); i +=2 ){
//cout << i << ' ' << Edges[i].first << ' ' << Edges[i].second << '\n';
Edge[Edges[i].first].push_back({Edges[i].second, i/2});
Edge[Edges[i].second].push_back({Edges[i].first, i/2});
Vis[i/2] = false;
}
vector < int > Sol;
for( int i = 1; i <= nodes; ++i ){
if( Edge[i].size() == 0 || Edge[i].size()%2 != 0 ){
Sol.push_back(-1);
return Sol;
}}
EulerianCircuitSearch(source, Edge, Vis, Sol );
Sol.pop_back();
return Sol;
}
void graph::EulerianCircuitSearch(int nod, vector<vector<pair<int, int>>> & Edge,
vector<bool> & Vis, vector<int> & Sol) {
int w, p;
while( !Edge[nod].empty() ){
w = Edge[nod].back().first;
p = Edge[nod].back().second;
Edge[nod].pop_back();
if( Vis[p] == false ){
Vis[p] = true;
EulerianCircuitSearch(w, Edge, Vis, Sol );
}
}
Sol.push_back( nod );
}
int graph::MinimumCostHamiltonianCircuit() {
vector < vector < int > > cost(nodes+1);
for( int i = 1; i <= nodes; ++i ) {
cost[i].resize(nodes+1);
for (int j = 0; j < Ad[i].size(); ++j)
cost[i][Ad[i][j]] = EdgeValue[i][j];
}
vector < vector < int > > dp( (1<<nodes) );
for( int mask = 0; mask <= (1<<nodes)-1; ++mask ) {
dp[mask].resize(nodes+1);
for (int i = 1; i <= nodes; ++i)
dp[mask][i] = INF;
}
dp[1][1] = 0;
for( int mask = 1; mask <= (1<<nodes)-1; ++mask )
for( int i = 1; i <= nodes; ++i ){
if( dp[mask][i] != INF )
for( int j = 1; j <= nodes; ++j )
if( cost[i][j] && !((1<<(j-1)) & mask) )
dp[((1<<(j-1)) | mask)][j] = min( dp[((1<<(j-1)) | mask)][j], dp[mask][i] + cost[i][j]);
}
long long sol = INF;
for( int i = 1; i <= nodes; ++i )
if( cost[i][1] )
sol = min(sol, 1LL*dp[(1 << nodes) - 1][i] + cost[i][1] );
return sol;
}
bool bipartiteGraph::Match(int nod, vector<int> &matchL, vector<int> &matchR, vector<bool> &vis) {
if( vis[nod] )
return false;
vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( !matchR[w] ){
matchL[nod] = w;
matchR[w] = nod;
return true;
}
}
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( Match(matchR[w], matchL, matchR, vis) ){
matchL[nod] = w;
matchR[w] = nod;
return true;
}
}
return false;
}
vector < pair < int, int > > bipartiteGraph::MaximumMatching() {
vector < bool > vis(nodes+1 );
vector < int > matchL( leftNodes+1, 0 );
vector < int > matchR ( rightNodes+1, 0 );
bool matchFound = true;
while( matchFound ) {
matchFound = false;
fill(vis.begin(), vis.end(), 0);
for (int i = 1; i <= leftNodes; ++i)
if (!matchL[i] && Match(i, matchL, matchR, vis))
matchFound = true;
}
vector < pair < int, int > > sol;
for( int i = 1; i <= leftNodes; ++i )
if( matchL[i] )
sol.push_back({i,matchL[i]});
return sol;
}
int main()
{
int N, M, E, x, y;
fin >> N >> M;
vector < vector < int > > ad(N+1);
for( int i = 1; i <= M; ++i ){
fin >> x >> y;
ad[x].push_back( y );
ad[y].push_back( x );
}
graph G(N,M,ad);
vector < vector < int > > sol = G.BiconnectedComponents();
fout << sol.size() << '\n';
for( int i = 0; i < sol.size(); ++i, fout << '\n' )
for( int j = 0; j < sol[i].size(); ++j )
fout << sol[i][j] << ' ';
return 0;
}