Codeforces Round #670 (Div. 2) C. Link Cut Centroids

admin管理员组

文章数量:1565349

题目链接

Fishing Prince loves trees, and he especially loves trees with only one centroid. The tree is a connected graph without cycles.

A vertex is a centroid of a tree only when you cut this vertex (remove it and remove all edges from this vertex), the size of the largest connected component of the remaining graph is the smallest possible.

For example, the centroid of the following tree is 2, because when you cut it, the size of the largest connected component of the remaining graph is 2 and it can’t be smaller.

However, in some trees, there might be more than one centroid, for example:

Both vertex 1 and vertex 2 are centroids because the size of the largest connected component is 3 after cutting each of them. Now Fishing Prince has a tree. He should cut one edge of the tree (it means to remove the edge). After that, he should add one edge. The resulting graph after these two operations should be a tree. He can add the edge that he cut. He wants the centroid of the resulting tree to be unique. Help him and find any possible way to make the operations. It can be proved, that at least one such way always exists.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤1e4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (3≤n≤1e5) — the number of vertices.

Each of the next n−1 lines contains two integers x,y (1≤x,y≤n). It means, that there exists an edge connecting vertices x and y.

It’s guaranteed that the given graph is a tree.

It’s guaranteed that the sum of n for all test cases does not exceed 1e5.

Output

For each test case, print two lines.

In the first line print two integers x1,y1 (1≤x1,y1≤n), which means you cut the edge between vertices x1 and y1. There should exist edge connecting vertices x1 and y1.

In the second line print two integers x2,y2 (1≤x2,y2≤n), which means you add the edge between vertices x2 and y2.

The graph after these two operations should be a tree.

If there are multiple solutions you can print any.

Example

input

2
5
1 2
1 3
2 4
2 5
6
1 2
1 3
1 4
2 5
2 6

output

1 2
1 2
1 3
2 3

图论~
这种题就是典型的找规律，当只存在一个重心时，就是任选一条边删去再添上即可。难点在于多个，我一开始以为树的重心就是连边最多的点，后来发现不对，树的重心应该坐落在某一个位置，该位置两端的点数应该趋于相同，以此推论我画了几棵树，发现重心要么一个要么两个，且两个时一定是连着的，那么我们以两个中的任意一个为父亲结点，另一个结点的子树大小一定是 n 2 \frac{n}{2} 2n​，所以只需要一遍 DFS 即可，当出现子树大小为 n 2 \frac{n}{2} 2n​，将该点的子树的任一点断开与父亲结点相连即可，此时重心一定只有一个了，这很好想，因为父亲结点所在的连通块大小加 1 1 1，所以父亲结点成为唯一的重心。AC代码如下:

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> G[N];
int n, t, u, v, son[N], flag;

void dfs(int u, int fa) {
    for (auto v:G[u]) {
        if (v != fa) {
            dfs(v, u);
            son[u] += son[v];
        }
    }
    if (flag && son[u] * 2 == n) {
        flag = 0;
        printf("%d %d\n%d %d\n", u, G[u][G[u][0] == fa], fa, G[u][G[u][0] == fa]);
    }
}

int main() {
    cin >> t;
    while (t--) {
        flag = 1;
        cin >> n;
        for (int i = 0; i <= n; i++) G[i].clear(), son[i] = 1;
        for (int i = 0; i < n - 1; i++) {
            cin >> u >> v;
            G[u].push_back(v), G[v].push_back(u);
        }
        dfs(1, -1);
        if (flag) printf("%d %d\n%d %d\n", 1, G[1][0], 1, G[1][0]);
    }
    return 0;
}

本文标签： DivcodeforcesCentroidsCutLINK