Submission #71366799

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
vector<int> G[N];
int B[N],Y[N],P[N],timer = 0,tin[N],tmin[N];
void dfs(int v,int par){
    tin[v] = tmin[v] = ++timer;
    B[v] = par;
    Y[v] = v;
    P[v] = par;
    for(int to:G[v]){
        if (to==par){
            continue;
        }
        if (tin[to]!=0){
            if (tmin[v]>tin[to]){
                tmin[v] = tin[to];
                Y[v] = to;
            }
        }
        else{
            dfs(to,v);
            if (tmin[v]>tmin[to]){
                tmin[v] = tmin[to];
                Y[v] = to;
            }
        }
    }
    // if Y[v]==v - bad case

}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<m;i+=1){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,1);
    int x = 2;
    while(x!=1){
        Y[P[x]] = x;
        x = P[x];
    }
    for(int i = 1;i<=n;i+=1){
        if (Y[i]==i && i!=2){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
    cout<<Y[1]<<'\n';
    cout<<B[2]<<'\n';
    for(int i = 3;i<=n;i+=1){
        cout<<B[i]<<' '<<Y[i]<<'\n';
    }
}  
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tt = 1;
    while(tt--){
        solve();
    }
}

Submission Info

Judge Result