题目描述

小 A 和小 B 玩游戏。小 A 有一个凸 $n$ 边形以及 $n-3$ 条不交的对角线构成一个三角剖分。每一次，小 B 可以问小 A 某一条对角线 $x-y$ ，小 A 会回答他该对角线是否在他的三角剖分中。小 B 想要对于每一条 三角剖分中 的对角线得到至少一次肯定的答复。他希望询问的次数尽量少，而小 A 希望询问次数尽量多，并且有可能会根据小 B 的询问来改变他的三角剖分。但在这个过程中，小 A 的三角剖分不能与他曾做出的回答矛盾。

现在，给出小 A 和小 B 玩的若干步，判断它们的游戏过程是否保持最优。如果是，输出 $0$；如果不是，输出第一次不是最优的操作，形如 A x 或者 B x，表示小 A 或者小 B 的第 $x$ 次操作不是最优的。

具体地，保持最优的定义如下：假设最优情况下小 B 要询问 $k$ 次，那么每一步过后，双方最优的策略仍然使得总的询问次数为 $k$，第一次使得询问次数不为 $k$ 的步骤就是需要输出的步骤。

他们玩了 $T$ 次独立的游戏，你需要对每一次询问作出回答。

注意：

• 数据保证，直到第一次不优的操作被做出，小 A 的回答都是合法的，即总存在一个三角剖分符合小 A 做出的所有回答。
• 数据不保证，在第一次不优的操作被做出以后，小 A 的回答仍然保持合法，即可能不存在一个三角剖分符合小 A 做出的所有回答。

【提示】

1. 多边形的对角线指连接不相邻两个顶点的线段。
2. 多边形的三角剖分指 $n-3$ 条仅可以在顶点处相交的对角线构成的集合。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每一组数据，第一行两个整数 $n,m$。

接下来 $m$ 行，每一行三个整数 $x,y,z$，表示小 B 的询问和小 A 的回答。其中 $z=0$ 表示该对角线不存在，$z=1$ 则表示存在。

输出格式

对于每组数据输出一行，若存在不优的操作则输出第一次不是最优的操作，否则输出 $0$。

5
4 2
1 3 0
2 4 1
5 4
2 5 0
1 4 0
3 1 1
2 4 0
5 4
1 3 0
2 4 1
2 5 0
1 4 1
5 4
1 3 0
5 3 0
1 4 1
2 5 0
4 2
1 3 0
1 3 1

0
B 4
0
B 2
B 2

提示

【样例解释】

对于 $n=5$，最优的 $k=4$。对于 $n=4$，最优的 $k=2$。对于最后一组数据，B 重复询问同一条边已经不是最优，此时 A 的回答可以不合法。

【数据范围】

$1 \le T\le 10^3$，$4\le n \le 10^5$，$1 \le \sum n \le 2\times 10^5$，$1 \le m \le k$，$1 \le x,y \le n$，$0 \le z \le 1$。保证所有的 $x-y$ 都是合法的对角线，以及直到第一次不是最优的一步所有询问的回答都至少对应一种三角剖分。

$$\def{\arraystretch}{1.5} \begin{array}{c|c|c|c|c}\hline \textbf{~~测试点编号~~}&\bm{~~T\le~~}&\bm{~~n \le ~~}&\bm{~~~~m~~~~}& ~\bm{z}~\cr\hline \textsf1\sim \sf2 &100 &5 & \cr\hline \sf3\sim 4 & 100& 7& &\cr\hline \sf5 \sim 6 &100 &8 & & \cr\hline \sf7 \sim \sf9 & & &=1 & \cr\hline \sf10\sim 12 & & & & =0\cr\hline \sf13\sim 16 &20 &200\cr\hline \sf 17 \sim 20 \end{array} $$