CF1819E.Roads in E City

This is an interactive problem.

As is well known, the city "E" has never had its roads repaired in its a thousand and a half years old history. And only recently the city administration repaired some of them.

It is known that in total in the city "E" there are $n$ intersections and $m$ roads, which can be used in both directions, numbered with integers from $1$ to $m$. The $i$-th road connects intersections with numbers $a_i$ and $b_i$.

Among all $m$ roads, some subset of the roads has been repaired, but you do not know which one. The only information you could get from the city's road services is that you can get from any intersection to any other intersection by driving only on the roads that have been repaired.

You are a young entrepreneur, and decided to organize a delivery service of fresh raw meat in the city "E" (in this city such meat is called "steaks", it is very popular among the locals). You have already recruited a staff of couriers, but the couriers are willing to travel only on repaired roads. Now you have to find out which roads have already been repaired.

The city administration has given you the city for a period of time, so you can make different queries of one of three types:

1. Block the road with the number $x$. In this case, movement on the road for couriers will be forbidden. Initially all roads are unblocked.
2. Unblock the road with the number $x$. In this case, couriers will be able to move on the road $x$ if it is repaired.
3. Try to deliver the order to the intersection with the number $y$. In this case, one of your couriers will start moving from intersection with number $s$ you don't know and deliver the order to intersection with number $y$ if there is a path on unblocked repaired roads from intersection $s$ to intersection $y$. It is guaranteed that intersection $s$ will be chosen beforehand.

Unfortunately, the city is placed at your complete disposal for a short period of time, so you can make no more than $100 \cdot m$ requests.

这是一个交互式问题。

众所周知，城市“E”在其一千五百年的历史中从未修缮过道路。直到最近，市政府才修缮了其中一部分道路。

已知城市“E”中共有 $n$ 个路口和 $m$ 条双向通行的道路，这些道路按整数编号为 $1$ 至 $m$。第 $i$ 条道路连接编号为 $a_i$ 和 $b_i$ 的两个路口。

在全部 $m$ 条道路中，有一部分子集已被修缮，但你并不知道具体是哪些。你唯一能从市政道路部门获取的信息是：仅通过已修缮的道路，即可从任意一个路口到达其余任意一个路口（即所有已修缮道路构成的子图是连通的）。

你是一位年轻的创业者，决定在城市“E”开办一项新鲜生肉配送服务（该城将此类生肉称为“牛排”，在当地居民中极为流行）。你已招募了一批快递员，但他们只愿意在已修缮的道路上行驶。现在，你需要确定哪些道路已被修缮。

市政府已将该城市短期交由你使用，因此你可以发出以下三种类型的查询请求：

1. 封锁编号为 $x$ 的道路。此时，快递员将禁止在该道路上通行。初始状态下，所有道路均处于未封锁状态。
2. 解除编号为 $x$ 的道路的封锁。此时，若该道路已被修缮，则快递员可再次在该道路上通行。
3. 尝试向编号为 $y$ 的路口配送订单。此时，你的某位快递员将从一个你未知的编号为 $s$ 的路口出发；若存在一条由未封锁且已修缮的道路构成的路径，从路口 $s$ 到达路口 $y$，则该快递员将成功完成配送。保证路口 $s$ 是预先选定的。

不幸的是，城市仅在极短时间内供你完全支配，因此你最多只能发出 $100 \cdot m$ 次查询请求。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1\,000$) — the number of test cases. The description of test cases follows.

The first line contains two integers $n$ and $m$ ($2 \le n \le 2\,000$, $n - 1 \le m \le 2\,000$) —the number of intersections and roads in the city "E".

Each of the following $m$ lines describes one road. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the ends of the $i$-th road. It is guaranteed that no road connects the city to itself, while it is possible that there are several roads between a pair of different intersections.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $2\,000$.

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

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2\,000$，$n - 1 \le m \le 2\,000$），分别表示城市“E”中的交叉路口数量和道路数量。

接下来的 $m$ 行每行描述一条道路。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示第 $i$ 条道路连接的两个端点。保证不存在连接同一交叉路口（即自环）的道路，但允许在两个不同交叉路口之间存在多条道路。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2\,000$。

In the first test case, road $1$ was repaired, while road $2$ was not. For the first delivery request, intersection $1$ was selected as $s$, and the path from intersection $1$ to $1$ exists. For the second delivery request, intersection $1$ was selected as $s$. Since the only repaired road was blocked, there was no path between intersections $1$ and $2$. For the third delivery request, intersection $2$ was selected as $s$, the path between intersections $2$ and $1$ exists along road $1$, which is repaired and unblocked.

In the second test case, intersections $1$, $3$, $1$, $2$, $2$, $3$, $1$ were selected as starting intersections for delivery requests.

在第一个测试用例中，道路 $1$ 被修复，而道路 $2$ 未被修复。对于第一个配送请求，交点 $1$ 被选为起点 $s$，从交点 $1$ 到 $1$ 的路径存在。对于第二个配送请求，交点 $1$ 被选为起点 $s$；由于唯一被修复的道路被阻塞，交点 $1$ 与交点 $2$ 之间不存在路径。对于第三个配送请求，交点 $2$ 被选为起点 $s$，交点 $2$ 与交点 $1$ 之间的路径沿道路 $1$ 存在，该道路已被修复且未被阻塞。

在第二个测试用例中，配送请求的起点交点依次为 $1$、$3$、$1$、$2$、$2$、$3$、$1$。