[GDKOI2024 普及组] 切割

Luogu
IDLGP10075
Time2000ms
Memory512MB
DifficultyP6
2024广东O2优化
给定一张 $n$ 个点 $m$ 条边的无向连通图,**有**重边无自环。 ymqOAO 现在有 $k$ 个询问。每次询问如果删去图中的 $c_i$ 条边,剩下的图是否还是连通的。 注意:询问之间是相互独立的,即一个询问的删边不会影响之后的询问。 注解: - 连通图:一个图中任意两个顶点都有路径相连。 ## Input 第一行输入三个整数 $n, m$。 接下来 $m$ 行,每行包含两个正整数 $x_i, y_i$,表示第 $i$ 条边为 $x_i$ 与 $y_i$ 所连的边。 接下来一行一个整数 $k$,表示询问的个数。 接下来 $k$ 行,第 $i$ 行的第一个整数 $c_i$ 表示所切割的边的条数,接下来 $c_i(1 \leq c_i \leq 4)$ 个整数,表示所切割的边的编号,其中边的编号范围为 $[1, m]$。 ## Output 对于每组询问,如果图不连通,则输出 `Bob`,否则输出 `ymqOAO`。(不包括引号) [samples] ## Note 对于 $10\%$ 的数据,$1 \leq m, n, k \leq 2000$。 对于另外 $10\%$ 的数据,$m = n-1$。 对于另外 $10\%$ 的数据,$c_i = 1$。 对于 $60\%$ 的数据,$1 \leq m, n, k \leq 10^5$。 对于 $100\%$ 的数据,$1 \leq m, n, k \leq 10^6$。
Samples
Input #1
4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Output #1
ymqOAO
Bob
ymqOAO
API Response (JSON)
{
  "problem": {
    "name": "[GDKOI2024 普及组] 切割",
    "description": {
      "content": "给定一张 $n$ 个点 $m$ 条边的无向连通图,**有**重边无自环。 ymqOAO 现在有 $k$ 个询问。每次询问如果删去图中的 $c_i$ 条边,剩下的图是否还是连通的。 注意:询问之间是相互独立的,即一个询问的删边不会影响之后的询问。 注解: - 连通图:一个图中任意两个顶点都有路径相连。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10075"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点 $m$ 条边的无向连通图,**有**重边无自环。\n\nymqOAO 现在有 $k$ 个询问。每次询问如果删去图中的 $c_i$ 条边,剩下的图是否还是连通的。\n\n注意:询问之间是相互独立的,即一个询问的删边不会影响之后的询问。\n\n注解:\n- 连通图:一个图中任意两个顶点都有路径相连。\n\n## Input\n\n第一行输入三个整数 $n, m$。\n\n接下来 $m$ 行,每行包含两个...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments