CF2181C.Cacti Classification

Ivan and Petr like to play with cacti — special graphs where each edge belongs to at most one simple cycle, and the graph is connected. Multiple edges between pairs of vertices and loops are allowed.

They invent the following game:

• Petr secretly builds a cactus with $n$ vertices and $m$ edges. The edges are labeled from $1$ to $m$.
• Petr only tells Ivan the number $m$.
• Ivan is then allowed to ask questions of the following form:
  • He chooses a subset $S$ of edge labels (see below about limitations on the subset), and asks: "If we only keep the edges whose labels are in $S$ (and all $n$ vertices), is the resulting graph connected?"
  • Petr must answer either "yes" or "no".

After asking at most $8m$ questions, Ivan must determine, for every edge:

1. whether this edge lies on some cycle in the cactus;
2. if it does, what is the length of that simple cycle.

In this problem, each loop is considered a simple cycle of length $1$ and two edges between the same pair of vertices form a simple cycle of length $2$.

However, Ivan is still very young and only knows numbers up to $14$. So:

• if an edge lies on a simple cycle of length at most $14$, he must output that exact length;
• if an edge lies on a simple cycle of length greater than $14$, he must say that this edge lies on a big cycle.

Also, to avoid having to list a lot of edges each time, Ivan always asks about an edge set obtained from the set used in one of the previous queries, or from the set of all edges, by removing exactly one edge.

Can you design a strategy that allows Ivan to complete this task?

伊万和彼得喜欢玩仙人掌图——一种特殊的图，其中每条边至多属于一个简单环，且整个图是连通的。允许在顶点对之间存在多重边，也允许存在自环。

他们设计了如下游戏：

• 彼得秘密构造一棵具有 $n$ 个顶点和 $m$ 条边的仙人掌图。这些边被依次标记为 $1$ 到 $m$。
• 彼得仅将数字 $m$ 告知伊万。
• 随后，伊万可以提出以下形式的问题（关于子集 $S$ 的限制见下文）：
  • 他选择一个边标签的子集 $S$，并提问：“若仅保留标签属于 $S$ 的边（以及全部 $n$ 个顶点），所得图是否连通？”
  • 彼得必须回答“是”或“否”。

在最多提出 $8m$ 个问题之后，伊万必须对每一条边确定：

1. 该边是否位于仙人掌图的某个简单环上；
2. 若是，则该简单环的长度是多少。

本题中，每个自环被视为长度为 $1$ 的简单环；连接同一对顶点的两条边构成长度为 $2$ 的简单环。

然而，伊万年纪尚小，只会处理不超过 $14$ 的数字。因此：

• 若某条边位于长度不超过 $14$ 的简单环上，则他必须输出该精确长度；
• 若某条边位于长度大于 $14$ 的简单环上，则他必须声明该边位于一个“大环”上。

此外，为避免每次均需列举大量边，伊万所询问的边集总是由前一次查询所用的边集、或由全体边集，通过恰好移除一条边而得到。

你能否设计一种策略，使伊万能完成此项任务？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains $m$ ($1 \le m \le 10^4$) — the number of edges in the cactus.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含 $m$（$1 \le m \le 10^4$）——即仙人掌图中的边数。

保证所有测试用例的 $m$ 值之和不超过 $10^4$。

In the example interaction, the input and output contain empty lines to align interactor responses with queries. These empty lines do not appear in the actual input and output.

In this example, the graph has $5$ vertices and $7$ edges; edges $1$ through $7$, in this order, are $(1, 2)$, $(2, 3)$, $(3, 3)$, $(3, 4)$, $(4, 5)$, $(2, 4)$, $(4, 5)$.

在示例交互中，输入和输出包含空行，以使交互器（interactor）的响应与查询对齐。这些空行不会实际出现在输入和输出中。

在本例中，图包含 $5$ 个顶点和 $7$ 条边；按顺序编号为 $1$ 至 $7$ 的边分别为 $(1, 2)$、$(2, 3)$、$(3, 3)$、$(3, 4)$、$(4, 5)$、$(2, 4)$、$(4, 5)$。