Embedding Trees into a Hypercube

Given an n-dimensional hypercube with vertices labeled from \(0\) to \(2^n-1\), where two vertices \(x\) and \(y\) are adjacent if and only if \(x \oplus y\) equals \(2^k\) for some non‐negative integer \(k\) (i.e. they differ in exactly one bit), you are also given several trees. Each tree has \(n+1\) nodes (labeled \(0,1,\dots,n\)) and exactly \(n\) edges. For each tree, you are given the endpoints of its \(n\) edges.

Your task is to assign each vertex of every tree to a vertex of the hypercube (a one‐to‐one mapping on that tree) so that:

• For every edge in the tree between vertices \(u\) and \(v\), the corresponding hypercube vertices \(f(u)\) and \(f(v)\) are adjacent in the hypercube (i.e. \(f(u) \oplus f(v)=2^k\) for some \(k\)).
• The images of the edges of different trees do not share any hypercube edge (i.e. each hypercube edge is used in at most one tree).

If there are multiple solutions, output any one valid placement scheme.

Note: A power of two is expressed in \(\LaTeX\) as \(2^k\) for some integer \(k \ge 0\).

inputFormat

The input begins with two integers \(n\) and \(t\) where \(n\) is the dimension of the hypercube and \(t\) is the number of trees.

Then, for each tree, there are exactly \(n\) lines. Each line contains two integers \(u\) and \(v\) (\(0 \le u,v \le n\)) indicating an edge between tree vertices \(u\) and \(v\).

It is guaranteed that each tree is a tree (i.e. it has \(n+1\) vertices and \(n\) edges).

outputFormat

For each tree, output a single line containing \(n+1\) integers. The \(i\)th integer in the line is the hypercube vertex (an integer from \(0\) to \(2^n-1\)) assigned to tree vertex \(i\) (\(0 \le i \le n\)).

The assignment for each tree must satisfy the condition that for every edge \((u,v)\) in the tree, \(f(u)\) and \(f(v)\) are adjacent in the hypercube. Moreover, the hypercube edges used across different trees must be disjoint.

sample

2 1
0 1
1 2

0 1 3