//pakage joney_000[let_me_start]
//
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
/*
 * Author    : joney_000[let_me_start]
 * Algorithm : N/A
 * Platform  : N/A
 *
 */


/*    The Main Class                */
class A
{ 
  private InputStream inputStream ;
  private OutputStream outputStream ;
  private FastReader in ;
  private PrintWriter out ;
  /*
    Overhead [Additional Temporary Strorage] but provides memory reusibility for multiple test cases.
    Size Limit : 10^5 + 4 
  */
  private final int BUFFER = 5;
  private int    tempints[] = new int[BUFFER];
  private long   templongs[] = new long[BUFFER];
  private double tempdoubles[] = new double[BUFFER];
  private char   tempchars[] = new char[BUFFER];
  //private final long mod = 1000000000+7;
  private final int  INF  = Integer.MAX_VALUE / 10;
  private final long INF_L  = Long.MAX_VALUE / 10;

  public A(){}
  public A(boolean stdIO)throws FileNotFoundException{
    // stdIO = false;
    if(stdIO){
      inputStream = System.in;
      outputStream = System.out;
    }else{
      inputStream = new FileInputStream("output.txt");
      outputStream = new FileOutputStream("output1.txt");
    }
    in = new FastReader(inputStream);
    out = new PrintWriter(outputStream);

  }
  int MAX_N = 200005;
  int n = 0; int m = MAX_N - 1;                       // tree = (v, e) 
  int level[]  = new int[MAX_N + 1];                  // l[v] = level of node v = et[i]
  
  int et[] = new int[3 * MAX_N + 1];                  // euler tour [1..2N] 
  int f[]  = new int[3 * MAX_N + 1];                  // f[v] = first occurence of node v in the et  
  int node[]  = new int[6 * MAX_N + MAX_N/100];       // Seg tree   size = 3 * (2N)
  
  LinkedList adj[] = new LinkedList[MAX_N + 1]; //Adjency List
  int index = 1;

  void run()throws Exception{
    int tests = i();
    once();
    for(int t = 1; t