package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	t := nextInt(scanner)
	for test := 0; test < t; test++ {
		n := nextInt(scanner)
		N := 1 << uint(n)
		m := n * (N / 2)
		adj := make([][]int, N)
		for i := 0; i < N; i++ {
			adj[i] = make([]int, 0, n)
		}
		for i := 0; i < m; i++ {
			u := nextInt(scanner)
			v := nextInt(scanner)
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		
		part := make([]int, N)
		for i := 0; i < N; i++ {
			part[i] = -1
		}
		var xlist, ylist []int
		bfsPart(0, adj, part, &xlist, &ylist)

		S := N / 2
		if len(xlist) != S || len(ylist) != S {
			
			continue
		}

		
		xIdx := make([]int, N)
		yIdx := make([]int, N)
		for i := 0; i < N; i++ {
			xIdx[i] = -1
			yIdx[i] = -1
		}
		for i := 0; i < S; i++ {
			xIdx[xlist[i]] = i
		}
		for i := 0; i < S; i++ {
			yIdx[ylist[i]] = i
		}

		
		out := make([][]int, S)
		for i := 0; i < S; i++ {
			origX := xlist[i]
			out[i] = adj[origX]
		}

		
		dimArr := make([][]int, S)
		for i := 0; i < S; i++ {
			dimArr[i] = make([]int, n)
			for j := 0; j < n; j++ {
				dimArr[i][j] = -1
			}
		}

		visited := make([][]bool, S)
		for i := 0; i < S; i++ {
			visited[i] = make([]bool, n)
		}

		curDim := 0
		for i := 0; i < S; i++ {
			for j := 0; j < n; j++ {
				if !visited[i][j] {
					bfsDim(i, j, curDim, out, visited, dimArr, adj, xlist, xIdx, n)
					curDim++
				}
			}
		}

		
		root := 0
		labels := make([]int, N)
		for i := 0; i < N; i++ {
			labels[i] = -1
		}
		labels[root] = 0
		q := make([]int, 0)
		q = append(q, root)
		vis := make([]bool, N)
		vis[root] = true
		qhead := 0
		for qhead < len(q) {
			u := q[qhead]
			qhead++
			for _, v := range adj[u] {
				bit := getDim(u, v, part, xIdx, out, dimArr, xlist, n)
				expected := labels[u] ^ (1 << bit)
				if labels[v] != -1 {
					if labels[v] != expected {
						
					}
					continue
				}
				labels[v] = expected
				if !vis[v] {
					vis[v] = true
					q = append(q, v)
				}
			}
		}

		
		P := make([]int, N)
		for orig := 0; orig < N; orig++ {
			lab := labels[orig]
			P[lab] = orig
		}

		
		builder := strings.Builder{}
		for i := 0; i < N; i++ {
			if i > 0 {
				builder.WriteString(" ")
			}
			builder.WriteString(strconv.Itoa(P[i]))
		}
		fmt.Println(builder.String())

		
		isPower := (n & (n - 1)) == 0 && n > 0
		if !isPower {
			fmt.Println(-1)
			continue
		}

		mm := 0
		tmp := n
		for tmp > 1 {
			tmp >>= 1
			mm++
		}

		standardCol := make([]int, N)
		for i := 0; i < N; i++ {
			col := 0
			for j := 0; j < mm; j++ {
				par := 0
				for k := 0; k < n; k++ {
					if ((i >> k) & 1) != 0 && ((k >> j) & 1) != 0 {
						par ^= 1
					}
				}
				if par != 0 {
					col |= (1 << j)
				}
			}
			standardCol[i] = col
		}

		colGiven := make([]int, N)
		for j := 0; j < N; j++ {
			colGiven[j] = standardCol[labels[j]]
		}

		builder = strings.Builder{}
		for i := 0; i < N; i++ {
			if i > 0 {
				builder.WriteString(" ")
			}
			builder.WriteString(strconv.Itoa(colGiven[i]))
		}
		fmt.Println(builder.String())
	}
}

func bfsPart(start int, adj [][]int, part []int, xlist, ylist *[]int) {
	q := []int{start}
	part[start] = 0
	*xlist = append(*xlist, start)
	qi := 0
	for qi < len(q) {
		u := q[qi]
		qi++
		for _, v := range adj[u] {
			if part[v] == -1 {
				part[v] = 1 - part[u]
				if part[v] == 0 {
					*xlist = append(*xlist, v)
				} else {
					*ylist = append(*ylist, v)
				}
				q = append(q, v)
			}
		}
	}
}

type pair struct {
	x int
	k int
}

func bfsDim(sx, sk, curDim int, out [][]int, visited [][]bool, dimArr [][]int, adj [][]int, xlist []int, xIdx []int, n int) {
	q := []pair{{sx, sk}}
	visited[sx][sk] = true
	dimArr[sx][sk] = curDim

	qi := 0
	for qi < len(q) {
		curr := q[qi]
		qi++

		a := xlist[curr.x]
		b := out[curr.x][curr.k]

		for _, d := range adj[a] {
			if d == b {
				continue
			}
			
			cprime := -1
			cnt := 0
			for _, cc := range adj[b] {
				found := false
				for _, dd := range adj[cc] {
					if dd == d {
						found = true
						break
					}
				}
				if found {
					cnt++
					if cc != a {
						cprime = cc
					}
				}
			}
			if cprime == -1 {
				continue
			}

			
			cx := xIdx[cprime]
			if cx == -1 {
				continue
			}
			var dk int
			found := false
			for dk = 0; dk < n; dk++ {
				if out[cx][dk] == d {
					found = true
					break
				}
			}
			if !found {
				continue
			}

			if !visited[cx][dk] {
				visited[cx][dk] = true
				dimArr[cx][dk] = curDim
				q = append(q, pair{cx, dk})
			}
		}
	}
}

func getDim(u, v int, part []int, xIdx []int, out [][]int, dimArr [][]int, xlist []int, n int) int {
	p1 := u
	p2 := v
	if part[p1] == 1 {
		p1 = v
		p2 = u
	}
	xi := xIdx[p1]
	for k := 0; k < n; k++ {
		if out[xi][k] == p2 {
			return dimArr[xi][k]
		}
	}
	return -1 
}

func nextInt(s *bufio.Scanner) int {
	s.Scan()
	x, _ := strconv.Atoi(s.Text())
	return x
}