have crushed Razor and presently, you are the Most Wanted road racer. Sergeant Cross has sent the full police power after you in a destructive pursuit. Luckily, you have discovered a concealing spot however you dread that Cross and his power will ultimately discover you. To build your odds of endurance, you need to tune
Correct answer will be upvoted else downvoted.
you have crushed Razor and presently, you are the Most Wanted road racer. Sergeant Cross has sent the full police power after you in a destructive pursuit. Luckily, you have discovered a concealing spot however you dread that Cross and his power will ultimately discover you. To build your odds of endurance, you need to tune and repaint your BMW M3 GTR.
The vehicle can be envisioned as a permuted n-dimensional hypercube. A straightforward n-dimensional hypercube is an undirected unweighted chart assembled recursively as follows:
Take two basic (n−1)- dimensional hypercubes one having vertices numbered from 0 to 2n−1−1 and the other having vertices numbered from 2n−1 to 2n−1. A basic 0-dimensional Hypercube is only a solitary vertex.
Add an edge between the vertices I and i+2n−1 for each 0≤i<2n−1.
A permuted n-dimensional hypercube is shaped by permuting the vertex numbers of a straightforward n-dimensional hypercube in any self-assertive way.
Input :The primary line of input contains a solitary integer t (1≤t≤4096) — the number of experiments. For each experiment, the main line contains a solitary integer n (1≤n≤16). Each of the following n⋅2n−1 lines contain two integers u and v (0≤u,v<2n) meaning that there is an edge between the vertices numbered u and v.
It is ensured that the chart depicted in the input is a permuted n-dimensional hypercube. Furthermore, it is ensured that the amount of 2n over all experiments doesn't surpass 216=65536.
Output :For each experiment, print two lines. In the principal line, output any stage P of length 2n that can be utilized to change a straightforward n-dimensional hypercube to the permuted n-dimensional hypercube given in the input. Two permuted hypercubes are viewed as something similar on the off chance that they have similar arrangement of edges. In case there are numerous replies, output any of them.
In the subsequent line, print the shading. In case it is absolutely impossible to shading the vertices fulfilling the conditions, output −1. In any case, output a solitary line containing 2n space isolated integers. The I-th integer should be the shade of the vertex numbered (i−1) in the permuted n-dimensional hypercube. In case there are numerous replies, output any of them.
Step by step
Solved in 4 steps with 1 images
