#include #include #include #include using namespace std; const int MAXN = 100000 + 5; int wn, w[5], w2[5], opposite, kv[MAXN], first_vote[MAXN], second_vote[MAXN], n, opt, Tn, sum_all; bool fail; /* A function that processes adding a vote from one of the friends. */ void process (int tag, int last) { if (tag == 0) { w[++wn] = opposite; } if (tag == 1) { int mi = 0; for(int i = 1; i <= n - 2; i++) if ((kv[mi] > kv[i] && i != last) || (i != last && mi == 0)) mi = i; w[++wn] = mi; if (mi == last || mi == 0) fail = true; } if (tag == 2) { int mi = 0; for(int i = 1; i <= n - 2; i++) if ((kv[mi] < kv[i] && i != last) || (i != last && mi == 0)) mi = i; w[++wn] = mi; if (mi == last || mi == 0) fail = true; } ++kv[w[wn]]; } /* This function checks whether the newly obtained answer is optimal. */ void check () { int mx = -1000000000; int mn = -mx; for(int i = 1; i <= n; i++) { mx = max(mx, kv[i]); mn = min(mn, kv[i]); } int qq = 0; if (mn < kv[n - 1] && kv[n - 1] < mx) ++qq; if (mn < kv[n] && kv[n] < mx) ++qq; if (qq > opt) { opt = qq; for(int j = 1; j <= wn; j++) w2[j] = w[j]; } } int main (int argc, char * const argv[]) { ios_base::sync_with_stdio(false); cin >> Tn; assert(1 <= Tn && Tn <= 100000); while (Tn--) { cin >> n; sum_all += n; assert(3 <= n && n <= 100000); for(int i = 1; i <= n - 2; i++) { cin >> first_vote[i]; } for(int i = 1; i <= n - 2; i++) cin >> second_vote[i]; for(int i = 1; i <= n - 2; i++) { assert(first_vote[i] != second_vote[i]); assert(first_vote[i] != i); assert(i != second_vote[i]); assert(1 <= first_vote[i] && first_vote[i] <= n); assert(1 <= second_vote[i] && second_vote[i] <= n); } /* kv[] corresponds to the number of votes one already have got. */ for(int i = 1; i <= n; i++) kv[i] = 0; for(int i = 1; i <= n - 2; i++) { ++kv[first_vote[i]]; ++kv[second_vote[i]]; } /* opt is the maximal number of participants that can be saved. It can be either 0, 1 or 2. In the code below, we brute-force all possible voting combinations for the first and the second guy (Devu and Amit). We consider that in the optimal solution is it reasonable to do one of three kinds of voting: - to vote for participant that has the maximal number of votes - to vote for participant that has the minimal number of votes - to vote for a friend (for Devu, to vote for Amit and vice-versa) */ opt = -1; for(int a1 = 1; a1 < 9; a1++) for(int a2 = 1; a2 < 9; a2++) { fail = false; wn = 0; int a11 = a1 / 3; int a12 = a1 % 3; int a21 = a2 / 3; int a22 = a2 % 3; opposite = n; process(a11, -1); process(a12, w[1]); opposite = n - 1; process(a21, -1); process(a22, w[3]); if (!fail) check(); for(int i = 1; i <= wn; i++) --kv[w[i]]; } kv[0] = -1; if (opt == 0) cout << "none" << endl; if (opt == 1) cout << "one" << endl; if (opt == 2) cout << "both" << endl; cout << w2[1] << " " << w2[2] << endl; cout << w2[3] << " " << w2[4] << endl; } assert(sum_all <= 1000000); return 0; }