[USACO22OPEN] Hoof and Brain P

Luogu
IDLGP8276
Time4000ms
Memory256MB
DifficultyP7
USACO2022拓扑排序启发式合并
给定一个包含 $N$ 个结点和 $M$ 条边的有向图($2 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$),Farmer John 的奶牛们喜欢玩以下的双人游戏。 在图中的不同结点上放置两个指示物(可以用一些与奶牛相关的物品代替指示物)。每一回合,一名玩家,脑,选择一个需要沿某一条出边移动的指示物。另一名玩家,蹄,选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动,则脑获胜。如果游戏可以无限进行下去,则蹄获胜。 给定 $Q$ 个询问($1 \leq Q \leq 10^5$),包含两个指示物所在的初始结点。对于每个询问,输出哪名玩家获胜。 ## Input 输入的第一行包含 $N$ 和 $M$。 以下 $M$ 行每行包含两个整数 $a$ 和 $b$,表示一条从 $a$ 连向 $b$ 的边。 图中不包含自环或重边。 下一行包含 $Q$。 最后 $Q$ 行每行包含两个整数 $x$ 和 $y$,满足 $1\le x,y\le N$ 以及 $x\neq y$,表示指示物所在的初始结点。 ## Output 输出一个长为 $Q$ 的字符串,其中字符 B 表示脑获胜,H 表示蹄获胜。 **注意:本题的时间限制为 4 秒,通常限制的两倍。** [samples] ## Note 【数据范围】 脑可以通过选择结点 $5$ 赢得第一局游戏;此时蹄将没有合法的行动。 脑可以通过选择结点 $4$ 然后选择结点 $7$ 赢得最后一局游戏;此时蹄没有合法的行动。 蹄赢得其他局游戏。 【测试点性质】 - 测试点 2-3 满足 $N\le 100$,$M\le 200$。 - 测试点 4-9 满足 $N\le 5000$。 - 测试点 10-21 没有额外限制。
Samples
Input #1
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4
Output #1
BHHB
API Response (JSON)
{
  "problem": {
    "name": "[USACO22OPEN] Hoof and Brain P",
    "description": {
      "content": "给定一个包含 $N$ 个结点和 $M$ 条边的有向图($2 \\leq N \\leq 10^5$, $1 \\leq M \\leq 2 \\cdot 10^5$),Farmer John 的奶牛们喜欢玩以下的双人游戏。 在图中的不同结点上放置两个指示物(可以用一些与奶牛相关的物品代替指示物)。每一回合,一名玩家,脑,选择一个需要沿某一条出边移动的指示物。另一名玩家,蹄,选择沿着哪条出边移动该指示物。两",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8276"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 $N$ 个结点和 $M$ 条边的有向图($2 \\leq N \\leq 10^5$, $1 \\leq M \\leq 2 \\cdot 10^5$),Farmer John 的奶牛们喜欢玩以下的双人游戏。\n\n在图中的不同结点上放置两个指示物(可以用一些与奶牛相关的物品代替指示物)。每一回合,一名玩家,脑,选择一个需要沿某一条出边移动的指示物。另一名玩家,蹄,选择沿着哪条出边移动该指示物。两...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments