题意：一个联通的无向图， 对于每一条边， 若删除该边后存在两点不可达，则输出这两个点， 如果存在多个则输出第一个点尽可能大，第二个点尽可能小的。 不存在输出0 0
首先 若删除某一条边后存在多个联通分量则该边一定是桥， 那么我们可以先处理出所有的桥，然后把所有双联通分量缩点，缩点之后就变成了一棵树。
而树上的每一条边都是一个桥， 考虑每条边的输出，删除某一边后肯定会出现两个联通分量， 需要记录两个联通分量中最大的点max1 max2， 如果max1！=n 则答案就是max1 max1+1否则max2 max2+1
现在的问题就转化为了如何求 不包含n的联通分量的最大值，因为两个联通分量肯定有一个联通分量的最大值为n， 所以 我们可以从包含n这个点的联通分量开始DFS， 每次遍历后更新一下，此时子树的最大值就是答案。
orz，第一次学习双联通分量。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ;
typedef pair <int, int>pii;
vector<pii>G[MAXN];
bool isBridge[MAXN];
int clk, pre[MAXN], low[MAXN];
int IDX, maxv[MAXN], newIdx[MAXN], newMax[MAXN];
int U[MAXN], V[MAXN];
int ans[MAXN];
bool vis[MAXN];
int n, m;
void init () {
memset(isBridge, false, sizeof (isBridge));
memset(pre, , sizeof (pre));
memset(low, , sizeof (low));
clk = ;
for (int i = ; i < MAXN; i++) {
G[i].clear();
}
}
void DFS (int u, int pa) {
int lowu = pre[u] = ++clk;
for (int i = ; i < G[u].size(); i++) {
pii e = G[u][i];
int v = e.first;
int idx = e.second;
if (!pre[v]) {
DFS(v, u);
lowu = min(lowu, low[v]);
if (low[v] > pre[u]) {
isBridge[idx] = true;
}
} else if (pre[v] < pre[u] && v != pa) {
lowu = min(lowu, pre[v]);
}
}
low[u] = lowu;
}
void DFS2(int u, int pa) {
vis[u] = true;
maxv[u] = u;
newIdx[u] = IDX;
for (int i = ; i < G[u].size(); i++) {
pii e = G[u][i];
int v = e.first;
int idx = e.second;
if (!isBridge[idx] && v != pa && !vis[v]) {
DFS2(v, u);
maxv[u] = max(maxv[u], maxv[v]);
}
}
}
void BCC_Bridge() {
DFS(, -);
memset(vis, false, sizeof (vis));
IDX = ;
for (int i = ; i <= n; i++) {
if (!vis[i]) {
IDX++;
DFS2(i, -);
}
}
for (int i = ; i <= n; i++) {
G[i].clear();
}
for (int i = ; i < m; i++) {
if (isBridge[i]) {
int u = newIdx[U[i]], v = newIdx[V[i]];
G[u].push_back(make_pair(v, i));
G[v].push_back(make_pair(u, i));
}
}
}
void solve (int u, int pa) {
pre[u] = ++clk;
ans[u] = newMax[u];
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i].first;
if (v != pa) {
solve(v, u);
ans[u] = max(ans[u], ans[v]);
} }
}
int main() {
int T;
scanf ("%d", &T);
while (T--) {
init();
scanf ("%d%d", &n, &m);
for (int i = ; i < m; i++) {
int u, v;
scanf ("%d%d", &u, &v);
U[i] = u, V[i] = v;
G[u].push_back(make_pair(v, i));
G[v].push_back(make_pair(u, i));
}
BCC_Bridge();
for (int i = ; i <= n; i++) {
newMax[newIdx[i]] = maxv[i];
}
int u;
for (u = ; u <= n; u++) {
if (newMax[u] == n) {
break;
}
}
memset(pre, , sizeof pre);
clk = ;
solve (u, );
for (int i = ; i < m; i++) {
int u = newIdx[U[i]], v = newIdx[V[i]];
if (u == v) {
printf("0 0\n");
} else {
if (pre[u] < pre[v]) {
swap(u, v);
}
printf("%d %d\n", ans[u], ans[u]+);
}
}
}
return ;
}