[HNOI2019] 校园旅行

HNOI2019 Day2T1

某学校的每个建筑都有一个独特的编号。一天你在校园里无聊，决定在校园内随意地漫步。 你已经在校园里呆过一段时间，对校园内每个建筑的编号非常熟悉，于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来，而是把每个建筑的编号除以 2 取余数得到 0 或 1，作为该建筑的标记，多个建筑物的标记连在一起形成一个 01 串。 你对这个串很感兴趣，尤其是对于这个串是回文串的情况，于是你决定研究这个问题。 学校可以看成一张图，建筑是图中的顶点，而某些顶点之间存在无向边。对于每个顶点我们有一个标记（0 或者 1）。每次你会选择图中两个顶点，你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。 一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同，比如 “010”，“1001” 都是回文串，而 “01”，“110” 不是。注意长度为 1 的串总是回文串，因此如果询问的两个顶点相同，这样的路径总是存在。此外注意，经过的路径不一定为简单路径，也就是说每条边每个顶点都可以经过任意多次。

输入文件名为 tour.in。 第一行三个整数 $n, m, q$，表示图中的顶点数和边数，以及询问数。 第二行为一个长度为 $n$ 的 01 串，其中第 $i$ 个字符表示第 $i$ 个顶点（即顶点 $i$）的标记，点从 1 开始编号。 接下来 $m$ 行，每一行是两个整数 $u_i, v_i$，表示顶点 $u_i$ 和顶点 $v_i$ 之间有一条无向边，不存在自环或者重边。 接下来 $q$ 行，每一行存在两个整数 $x_i, y_i$，表示询问顶点 $x_i$ 和顶点 $y_i$ 的点之间是否有一条满足条件的路径。

输出文件名为 tour.out。 输出 $q$ 行，每行一个字符串 “YES”，或者 “NO”（引号不输出）。输出 “YES” 表示满足条件的路径存在，输出 “NO” 表示不存在。

5 4 2
00010
4 5
1 3
4 2
2 5
3 5
1 3

NO
YES

10 11 10
0011011111
4 6
10 6
5 9
4 7
10 7
5 8
1 9
5 7
1 10
5 1
5 6
10 3
7 4
8 10
9 4
8 9
6 6
2 2
9 9
10 9
3 4

NO
YES
YES
NO
YES
YES
YES
YES
YES
NO

【样例解释 1】 对于第一个询问，3 号点和 2 号点不连通，因此答案为 “NO”。 对于第二个询问，一条合法的路径是 1→3，路径上的标号形成的字符串为 “00”。注意合法路径不唯一。 【数据范围】 对于 $30\%$ 的数据，$1 \leq m \leq 10 ^ 4$； 对于 $70\%$ 的数据，$1 \leq n \leq 3000$，$1 \leq m \leq 5\times 10 ^ 4$； 对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq m \leq 5\times 10 ^ 5$，$1 \leq q \leq 10 ^ 5$。 【编译命令】 对于 c++ 语言：g++ -o tour tour.cpp –lm -O2 对于 c 语言：gcc -o tour tour.c –lm -O2 对于 pascal 语言：fpc tour.pas -O2