P9163 "INOH" Round 1 - Knot

 The figure above shows the planar projections of two knots. We observe that a knot can be described by basic crossing points, and each crossing point is a double point. That is, we can **use a point to represent a crossing, and connect crossings with edges of different types**. You can see that **each point has four exits, and exits are connected to exits**. Among these four edges, **two are on the upper layer and two are on the lower layer**. We use an ordered pair $(u, d)$ to represent such an exit. Here, $u$ is the index of the point, and $d \in [0, 3]$. Also, **we define that $0$ and $1$ are the two upper edges, and $2$ and $3$ are the two lower edges**. We also observe that a knot has two ends. These two ends can be connected to the outside. For convenience, we **use $(-1, 0)$ and $(-2, 0)$ to represent these two ends**. Now you are given such a knot. You need to answer: when we pinch the two ends and pull hard, is it a slipknot (live knot) or a dead knot? If it is a slipknot, output `Yes`. If it is a dead knot, output `No`.

The first line contains the number of test cases $T$. For each test case, the first line contains $n$, the number of nodes. Then follow $n$ lines. On the $i$-th line there are eight integers $u_0, d_0, u_1, d_1, u_2, d_2, u_3, d_3$, describing the corresponding exits connected to exits $0$ through $3$ of node $i$. In the $i$-th line, the first pair $(u_0, d_0)$ means that exit $0$ of node $i$ is connected to exit $d_0$ of node $u_0$, and so on.

Output $T$ lines in total. Each line is `Yes` or `No`.

### Constraints **This problem uses bundled testdata**. - Subtask 0 (20 pts): $T = 3$, $1 \le n \le 10$. - Subtask 1 (20 pts): $T = 10^3$, $1 \le n \le 10$. - Subtask 2 (10 pts): $T = 10$, $1 \le n \le 10^5$, and the testdata is guaranteed to be randomly generated. - Subtask 3 (50 pts): $T = 10$, $1 \le n \le 10^5$. ### Sample Explanation In sample 1 (the left figure), it is a dead knot. In sample 2 (the right figure), it is a slipknot (live knot).  Translated by ChatGPT 5