题目详情题解（0）讨论（0）提交记录（0）

AT_agc027_c.[AGC027C] ABland Yard

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个包含 NN 个顶点和 MM 条边的无向图。顶点编号为 11 到 NN，边编号为 11 到 MM。每个顶点除了编号外，还带有一个标签 A 或 B，顶点 ii 的标签为 sis_i。

第 ii 条边连接顶点 aia_i 和 bib_i，且是双向的。

怪盗ヌ斯克喜欢从任意一个顶点出发，经过 00 次或多次沿边移动。今天，他想在移动后，将访问过的顶点的标签，按照从起点开始访问的顺序排列，组成一个字符串。

例如，在一个顶点 11 的标签为 A，顶点 22 的标签为 B 的图中，如果ヌ斯克按照 1→2→1→2→21\rightarrow2\rightarrow1\rightarrow2\rightarrow2 的顺序移动，则可以得到字符串 ABABB。

请判断怪盗ヌ斯克是否能够构造出任意由 A 和 B 组成的字符串。

输入格式

输入通过标准输入给出，格式如下：

NN MM ss a1a_1 b1b_1 ⋯\cdots aMa_M bMb_M

输出格式

如果ヌ斯克能够构造出任意由 A 和 B 组成的字符串，则输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    2 3
AB
1 1
1 2
2 2

    输出#1

    Yes

  • 输入#2

    4 3
ABAB
1 2
2 3
3 1

    输出#2

    No

  • 输入#3

    13 23
ABAAAABBBBAAB
7 1
10 6
1 11
2 10
2 8
2 11
11 12
8 3
7 12
11 2
13 13
11 9
4 1
9 7
9 6
8 13
8 6
4 10
8 7
4 3
2 1
8 12
6 9

    输出#3

    Yes

  • 输入#4

    13 17
BBABBBAABABBA
7 1
7 9
11 12
3 9
11 9
2 1
11 5
12 11
10 8
1 11
1 8
7 7
9 10
8 8
8 12
6 2
13 11

    输出#4

    No

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^{5}
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^{5}
  • ∣s∣=N|s| = N
  • sis_i 为 A 或 B
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 给定的图不一定是简单图，也不一定是连通图

样例解释 1

  • ヌ斯克可以自由地访问顶点 11 和顶点 22，因此可以构造出任意由 A 和 B 组成的字符串。

样例解释 2

  • 例如，无法构造出 BB。给定的图不一定是连通图。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页