P8566 You are the Miserable.

Little A and Little B are playing a game. Little A has a convex $n$-gon and a triangulation formed by $n-3$ non-intersecting diagonals. Each time, Little B may ask Little A about some diagonal $x-y$, and Little A will answer whether this diagonal is in his triangulation. Little B wants to obtain at least one affirmative answer for every diagonal **in the triangulation**. He wants to ask as few questions as possible, while Little A wants the number of questions to be as large as possible, and may even change his triangulation according to Little B’s questions. However, during this process, Little A’s triangulation must not contradict any answers he has given before. Now you are given several steps of the game between Little A and Little B. Determine whether their gameplay remains optimal. If yes, output $0$; otherwise, output the first non-optimal move in the form `A x` or `B x`, meaning that Little A’s or Little B’s $x$-th move is not optimal. More specifically, the definition of “remaining optimal” is as follows: suppose that under optimal play Little B needs to ask $k$ times. Then after every step, if both sides continue to play optimally, the total number of questions is still $k$. The first step that makes the number of questions no longer equal to $k$ is the step you should output. They played $T$ independent games, and you need to answer for each game. **Note:** - The testdata guarantees that, until the first non-optimal move is made, Little A’s answers are legal, i.e. there always exists a triangulation consistent with all of Little A’s answers. - The testdata does not guarantee that after the first non-optimal move is made, Little A’s answers are still legal, i.e. there may be no triangulation consistent with all of Little A’s answers. **Hint** 1. A polygon diagonal refers to a line segment connecting two non-adjacent vertices. 2. A polygon triangulation refers to a set of $n-3$ diagonals that may only intersect at vertices.

The first line contains an integer $T$, indicating the number of test cases. For each test case, the first line contains two integers $n, m$. The next $m$ lines each contain three integers $x, y, z$, representing Little B’s query and Little A’s answer. Here $z=0$ means the diagonal does not exist, and $z=1$ means it exists.

For each test case, output one line. If there is a non-optimal move, output the first move that is not optimal; otherwise output $0$.

[Sample Explanation] For $n=5$, the optimal $k=4$. For $n=4$, the optimal $k=2$. For the last test case, B repeatedly asks the same edge, which is already not optimal. At this point A’s answers may be illegal. [Constraints] $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$. It is guaranteed that all $x-y$ are valid diagonals, and until the first step that is not optimal, all answers correspond to at least one triangulation. $$ \def\arraystretch{1.5} \begin{array}{c|c|c|c|c}\hline \textbf{~~Test Point ID~~}&\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} $$ Translated by ChatGPT 5