Pagini recente » Cod sursa (job #952022) | Cod sursa (job #2314889) | Cod sursa (job #424593) | Cod sursa (job #2678170) | Cod sursa (job #2513648)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#define N 100005
#define ll long long
#define f first
#define s second
using namespace std;
ifstream in("in.txt");
ofstream out("out.txt");
vector<pair<ll,ll>> a[N], mu;
vector<ll> rez[2*N];
set<ll> sol[2*N];
stack<ll> st;
bool v[N], vm[2*N];
ll k=0;
void dfsm(ll i){
vm[i]=1;
sol[k].insert(mu[i].f);
sol[k].insert(mu[i].s);
for(auto it:rez[i])
if(!vm[it])
dfsm(it);
}
void dfs(ll i, ll j){
v[i]=1;
for(auto it:a[i])
if(!v[it.f]){
st.push(it.s);
dfs(it.f, it.s);
}
else if(v[it.f] && j!=it.s){
for(auto itt:a[it.f])
if(vm[itt.s]){
rez[it.s].push_back(itt.s);
rez[itt.s].push_back(it.s);
}
vm[it.s]=1;
while(!st.empty()){
rez[it.s].push_back(st.top());
rez[st.top()].push_back(it.s);
vm[st.top()]=1;
if(mu[st.top()].f==it.f || mu[st.top()].s==it.f)
break;
st.pop();
}
}
while(!st.empty() && st.top()!=j)
st.pop();
}
int main() {
ll n, m,i,x,y;
in>>n>>m;
for(i=0; i<m; ++i){
in>>x>>y;
a[x].push_back({y,i});
a[y].push_back({x,i});
mu.push_back({x,y});
}
dfs(1,-1);
for(i=0; i<m; ++i)
vm[i]=0;
for(i=0; i<m; ++i)
if(!vm[i]){
dfsm(i);
++k;
}
out<<k<<"\n";
for(i=0; i<k; ++i){
for(auto it:sol[i])
out<<it<<" ";
out<<"\n";
}
return 0;
}