{"raw_statement":[{"iden":"problem statement","content":"You are given a connected simple undirected graph with $N$ vertices and $\\displaystyle\\frac{3}{2}N$ edges, where $N$ is a positive **even number**. The vertices are labeled from $1$ to $N$, and the $i$\\-th edge connects vertex $A_i$ and vertex $B_i$. Moreover, for every vertex, the **number of incident edges is exactly $3$**.\nYou will color each vertex of the given graph either black ( `B` ) or white ( `W` ). Here, the string obtained by arranging the colors ( `B` or `W` ) of the vertices in the order of vertex labels is called a **color sequence**.\nDetermine whether there is a color sequence that **cannot** result from performing the following operation once when all vertices are colored, and if there is such a color sequence, find one.\n**Operation:** For each vertex $k = 1, 2, \\dots, N$, let $C_k$ be the color that occupies the majority (more than half) of the colors of the vertices connected to $k$ by an edge. For every vertex $k$, change its color to $C_k$ simultaneously.\nThere are $T$ test cases to solve."},{"iden":"constraints","content":"*   $T \\geq 1$\n*   $N \\geq 4$\n*   The sum of $N$ over the test cases in each input file is at most $5 \\times 10^4$.\n*   $N$ is an **even number**.\n*   $1 \\leq A_i < B_i \\leq N \\ \\ \\left(1 \\leq i \\leq \\displaystyle\\frac{3}{2}N\\right)$\n*   $(A_i, B_i) \\neq (A_j, B_j) \\ \\ \\left(1 \\leq i < j \\leq \\displaystyle\\frac{3}{2}N\\right)$\n*   The given graph is connected.\n*   Each vertex $k \\ (1 \\leq k \\leq N)$ appears **exactly $3$ times** as $A_i, B_i \\ \\left(1 \\leq i \\leq \\displaystyle\\frac{3}{2}N\\right)$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case $\\mathrm{case}_i \\ (1 \\leq i \\leq T)$ is in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{\\frac{3}{2}N}$ $B_{\\frac{3}{2}N}$"},{"iden":"sample input 1","content":"2\n4\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n10\n1 2\n1 3\n1 4\n2 3\n2 4\n3 5\n4 5\n5 6\n6 7\n6 8\n7 9\n7 10\n8 9\n8 10\n9 10"},{"iden":"sample output 1","content":"BWWW\nBWWWBWWWBB\n\nLet us consider the first test case. For the color of vertex $1$ to be `B`, at least two of the colors of vertices $2, 3, 4$ must be `B` before the operation. Then, for at least one of the vertices $2, 3, 4$, at least two of the colors of the vertices connected to that vertex by an edge are `B`, so the color of that vertex after the operation will be `B`. Therefore, the color sequence `BWWW` cannot result from performing the operation."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}