「INOH」Round 1 - 纽结

Luogu

IDLGP9163

Time1000ms

Memory128MB

DifficultyP5

O2优化

![](https://cdn.luogu.com.cn/upload/image_hosting/edc1559k.png) 上图是两个结的平面投影图。我们发现一个结可以由基本的重叠点描述，并且每一个重叠点都是二重点。也就是说我们可以用**一个点表示重叠点，重叠点之间用不同属性的边来连接**。可以发现**一个点有四个出口，出口与出口相连**，这四条中有**两条在上，两条在下**。我们用一个二元组 $(u,d)$ 表示这样一个出口。其中 $u$ 为这个点，$d \in [ 0, 3 ] $，同时**钦定 $0$ 和 $1$ 为两条上边，$2$ 和 $3$ 为两条下边**。又发现一个结有两端，这两端一定可以与外界相连，为了方便，用 **$(-1,0)$ 和 $(-2,0)$ 表示这两端**。现在给您一个这样的结，您需要回答，当我们手捏两端，然后用力拉，这是个活结还是死结？如果是活结请输出 `Yes`，如果是死结请输出 `No`。 ## Input 第一行为数据组数 $T$。每组数据第一行 $n$，表示结点数。之后 $n$ 行，第 $i$ 行有 $ u_0, d_0, u_1, d_1, u_2, d_2, u_3, d_3 $ 共八个数分别为第 $i$ 个点的 $0$ 到 $3$ 号出口连向的对应出口。第 $i$ 行的第 0 组 $(u_0,d_0)$ 指第 $i$ 个点的 $0$ 号出口与第 $u_0$ 个点的 $d_0$ 号出口相连，以此类推。 ## Output 一共 $T$ 行，每行为 `Yes` 或 `No`。 [samples] ## Note ### 数据范围 **本题采用捆绑测试**。 - Subtask 0（20pts）：$T = 3$，$1 \le n \le 10$。 - Subtask 1（20pts）：$T = 10^3$，$1 \le n \le 10$。 - Subtask 2（10pts）：$T = 10$，$1 \le n \le 10^5$，且保证数据随机生成。 - Subtask 3（50pts）：$T = 10$，$1 \le n \le 10^5$。 ### 样例解释：样例一为左图，它是死结。样例二为右图，它是活结。 ![](https://cdn.luogu.com.cn/upload/image_hosting/zkq4wmsn.png)

Samples

Input #1

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

Output #1

No

Input #2

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

Output #2

Yes

API Response (JSON)

{
  "problem": {
    "name": "「INOH」Round 1 - 纽结",
    "description": {
      "content": "![](https://cdn.luogu.com.cn/upload/image_hosting/edc1559k.png)   上图是两个结的平面投影图。   我们发现一个结可以由基本的重叠点描述，并且每一个重叠点都是二重点。   也就是说我们可以用**一个点表示重叠点，重叠点之间用不同属性的边来连接**。   可以发现**一个点有四个出口，出口与出口相连**，这四条中有**两条在上，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9163"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "![](https://cdn.luogu.com.cn/upload/image_hosting/edc1559k.png)  \n\n上图是两个结的平面投影图。  \n\n我们发现一个结可以由基本的重叠点描述，并且每一个重叠点都是二重点。  \n\n也就是说我们可以用**一个点表示重叠点，重叠点之间用不同属性的边来连接**。  \n\n可以发现**一个点有四个出口，出口与出口相连**，这四条中有**两条在上，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments