#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(3)
#define debug(x...)             \
    do {                      \
        cout << #x << " -> ";\
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template<class T, class... Ts>
void err(const T &arg, const Ts &... args) {
    cout << arg << ' ';
    err(args...);
}

const ll INF = 0x3f3f3f3f3f3f3f3f;//2147483647;
const ll MOD[2] = {1000000007, 998244353};
const ll base[2] = {131, 13331};
const double pi = acos(-1.0);

const int N = 25050, M = 5050 << 1;
const ll mod = MOD[0];

int n;

void dfs(int x, int pre, vector<vector<int>> &to, vector<int> &vis, stack<int> &stk, vector<int> &loop) {
    if (!loop.empty())return;
    for (auto v: to[x]) {
        if (v == pre)continue;
        if (vis[v]) {
            while (!stk.empty() && stk.top() != v) {
                loop.push_back(stk.top());
                stk.pop();
            }
            loop.push_back(v);
            return;
        }
        stk.push(v);
        vis[v] = 1;
        dfs(v, x, to, vis, stk, loop);
        if (!loop.empty())return;
        stk.pop();
        vis[v] = 0;
    }
}

int DFS(int x, int pre, vector<vector<int>> &to, vector<int> &vis) {
    if (to[x].size() == 1)return 1;
    int res = 0;
    for (auto v: to[x]) {
        if (v == pre)continue;
        if (vis[v])continue;
        res += DFS(v, x, to, vis);
    }
    return res;
}

void solve() {
    cin >> n;
    vector<vector<int>> G(n + 1, vector<int>());
    for (int i = 1, u, v; i <= n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> vis(n + 1, 0);
    stack<int> stk;
    stk.push(1);
    vis[1] = 1;
    vector<int> loop;
    dfs(1, 0, G, vis, stk, loop);
    for (auto i: loop) {
        cout << i << " ";
    }
    cout << "\n";
    vector<int> in_loop(n + 1, 0);
    for (auto i: loop) {
        in_loop[i] = 1;
    }
    vector<int> cal(n + 1, 0);
    int ans = 3;
    for (auto i: loop) {
        cal[i] = DFS(i, 0, G, in_loop);
    }
    int res = 0;
    int neighbor = 0;
    for (int i = 0; i < (int) loop.size(); i++) {
        if (cal[loop[i]]) {
            res += cal[loop[i]];
        } else {
            int nxt = loop[(i + 1) % (int) loop.size()];
            if (!cal[nxt])neighbor = 1;
        }
    }
    if (neighbor) {
        ans = max(ans, res + 2);
    } else {
        ans = max(ans, res + 1);
    }
    cout << ans << "\n";
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    for (int i = 1; i <= _; i++) {
        solve();
    }
    return 0;
}
/*
1
6
3 2
4 1
4 6
2 1
2 6
5 1
*/