This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Os")
#include <bits/stdc++.h>
using namespace std;
vector<int> p1, r1, p2, r2;
int get1(int i) {
if (p1[i]!=i && p1[i]!=p1[p1[i]]) p1[i]=get1(p1[i]);
return p1[i];
}
inline bool unite1(int a,int b) {
a=get1(a),b=get1(b);
if (a==b)return false;
if (r1[a]<r1[b])swap(a,b);
p1[b]=a;
if (r1[a]==r1[b])r1[a]++;
return true;
}
int get2(int i) {
if (p2[i]!=i && p2[i]!=p2[p2[i]]) p2[i]=get2(p2[i]);
return p2[i];
}
inline bool unite2(int a,int b) {
a=get2(a),b=get2(b);
if (a==b)return false;
if (r2[a]<r2[b])swap(a,b);
p2[b]=a;
if (r2[a]==r2[b])r2[a]++;
return true;
}
#define MAXN 100000
vector<int> st(MAXN, 0);
vector<vector<int>> g;
vector<vector<int>> lft;
bitset<100000> vis;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;cin>>n>>m;
p1.assign(n,0);r1.assign(n,0);p2.assign(n,0);r2.assign(n,0);
g.assign(n, vector<int>());
for (int i=0;i<n;i++) {
p1[i]=i;
p2[i]=i;
}
for (int i=0;i<m;i++) {
int a,b;cin>>a>>b;a--;b--;
if (unite1(a,b)) {
g[a].push_back(b);
g[b].push_back(a);
}
else {
unite2(a,b);
}
}
r1.assign(n,0);
lft.assign(n, vector<int>(18,-1));
for (int i=0;i<n;i++) {
if (vis[i]) continue;
int pt=0;
st[pt]=i;
vis[i]=true;
while (pt != -1) {
int r=st[pt--];
for (int x:g[r]) {
if (!vis[x]) {
vis[x]=true;
lft[x][0]=r;
r1[x]=r1[r]+1;
st[++pt]=x;
}
}
}
}
for (int j=1;j<18;j++) {
for (int i=0;i<n;i++) {
lft[i][j]=lft[i][j-1];
if (lft[i][j] != -1) {
lft[i][j]=lft[lft[i][j]][j-1];
}
}
}
r2.assign(n,0);
for (int i=0;i<n;i++) {
if (p2[i] == i) continue;
int a=i, b=get2(i);
r2[a]++;
r2[b]++;
if (r1[a]<r1[b])swap(a,b);
int steps=r1[a]-r1[b];
int cnt=0;
while (steps) {
if ((steps&1)==1) {
a=lft[a][cnt];
}
steps>>=1;cnt++;
}
if (a==b) {
r2[a]-=2;
continue;
}
for (int j=17;j>-1;--j) {
if (lft[a][j] != lft[b][j]) {
a=lft[a][j];
b=lft[b][j];
}
}
r2[lft[a][0]] -= 2;
}
for (int i=0;i<n;i++) {
lft[i]={lft[i][0]};
}
for (int i=0;i<n;i++) vis[i]=0;
for (int i=0;i<n;i++) {
st[i]=-1;
}
for (int i=0;i<n;i++) {
if (vis[i])continue;
int pt=0;
vis[i]=true;
st[0]=i;
while (pt != -1) {
int r=st[pt];
if (g[r].size()==0) {
if (lft[r][0] != -1) {
r2[lft[r][0]] += r2[r];
}
pt--;
continue;
}
for (int x:g[r]) {
if (!vis[x]) {
st[++pt]=x;
vis[x]=true;
}
}
g[r].clear();
}
}
for (int i=0;i<n;i++) {
if (r2[i]==0 && lft[i][0] != -1) {
cout<<i+1<<" "<<lft[i][0]+1<<"\n";
}
}
r2.clear();
lft.clear();
r1.clear();
p2.clear();
p1.clear();
st.clear();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |