Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define TASK "BLUEHOUSE"
- #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
- #define READFILE freopen(TASK".INP","r",stdin)
- #define WRITEFILE freopen(TASK".OUT","w",stdout)
- #define For(i,a,b) for(int i=a;i<=b;i++)
- #define Rep(i,a,b) for(int i=a;i>=b;i--)
- #define pb push_back
- #define ENDL '\n'
- #define debug(x) cout<<#x<<" = "<<x<<ENDL
- #define fi first
- #define se second
- #define ever (;true;)
- #define all(x) x.begin(),x.end()
- #define sz(a) ((int)(a).size())
- #define ms(a,x) memset(a,x,sizeof(a))
- #define int long long
- using namespace std;
- typedef vector <int> vi;
- typedef pair <int,int> ii;
- typedef vector <ii> vpi;
- typedef pair <int,ii> iii;
- const int N = 50010;
- const int oo=0x3f;
- const int mod=1e9+7;
- const int dx[]={0,1,0,-1,0};
- int n,m,num[N],low[N],f[N],cnt,scc,tp[N],s[5];
- vpi edge;
- vi a[N],g[N];
- stack<int> st;
- void dfs(int u, int p){
- num[u]=low[u]=++cnt;
- st.push(u);
- for (int v:g[u]){
- if (v==p) continue;
- if (num[v]) low[u]=min(low[u],num[v]);
- else {
- dfs(v,u);
- low[u]=min(low[u],low[v]);
- if (low[v]>=num[v]) edge.pb({u,v});
- }
- }
- if (low[u]==num[u]){
- int v;
- scc++;
- f[scc]=u;
- do{
- v=st.top();
- st.pop();
- tp[v]=scc;
- } while (v!=u);
- }
- }
- void dfs2(int u, int p){
- if (a[u].size()==1 && u!=1) st.push(u);
- for (int v:a[u]){
- if (v==p) continue;
- dfs2(v,u);
- }
- }
- void init(){
- FAST;
- #ifndef ONLINE_JUDGE
- READFILE;
- WRITEFILE;
- #endif
- cin >> n >> m;
- For(i,1,m){
- int u,v;
- cin >> u >> v;
- g[u].pb(v);
- g[v].pb(u);
- }
- }
- signed main()
- {
- init();
- dfs(1,-1);
- for (ii s : edge){
- int u=s.fi;
- int v=s.se;
- a[tp[u]].pb(tp[v]);
- a[tp[v]].pb(tp[u]);
- }
- dfs2(1,-1);
- stack<ii> ss;
- cnt=0;
- while (st.size()){
- s[++cnt]=st.top();
- st.pop();
- if (cnt==3){
- ss.push({f[s[1]],f[s[3]]});
- cnt=1;
- s[1]=s[2];
- }
- }
- if (cnt==2) ss.push({f[s[1]],f[s[2]]});
- if (cnt==1 || a[1].size()==1) {
- ss.push({f[s[1]],f[1]});
- a[1].pb(2);
- }
- cout << ss.size() << ENDL;
- while (ss.size()){
- cout << ss.top().fi << ' ' << ss.top().se << ENDL;
- ss.pop();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement