Problem Description

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.

Input Format

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 Format

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

1
3
-1 0 2 2 2 0 3 0
1 2 3 2 1 1 3 1
1 3 2 3 2 1 -2 0

No

1
3
-1 0 2 0 2 2 3 0
1 1 3 1 1 2 3 2
1 3 2 1 2 3 -2 0

Yes

Hint

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