某学校的每个建筑都有一个独特的编号。一天你在校园里无聊，决定在校园内随意的漫步。

你已经是在校园里呆过一段时间的人，对校园内每个建筑的编号非常熟悉，于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来，而是把每个建筑的编号除以2取余数得到0或1，作为该建筑的标记，多个建筑物的标记连在一起形成一个01串。

你对这个串很感兴趣，尤其是对于这个串是回文串的情况，于是你决定研究这个问题 。 学校可以看成一张图，建筑是图中的顶点，而某些顶点之间存在无向边。对于每个顶点我们有一个标记（0或者1）。每次你会选择图中两个顶点，你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。

一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同，比如“010”，“1001”都是回文串，而“01”，“110”不是。注意长度为1的串总是回文串，因此如果询问的两个顶点相同，这样的路径总是存在。此外注意，经过的路径不一定为简单路径，也就是说每条边每个顶点都可以经过任意多次。

输入格式

第一行三个整数$n,m,q$，表示图中的顶点数和边数，以及询问数。

第二行为一个长度为n的01串，其8中第$i$个字符表示第$i$个顶点（即顶点$i$）的标记，点从1开始编号。

接下来$m$行，每一行是两个整数$u_i,v_i$，表示顶点$u_i$和顶点$v_i$之间有一条无向边，不存在自环或者重边。

接下来$q$行，每一行存在两个整数$x_i,y_i$，表示询问顶点$x_i$和顶点$y_i$的点之间是否有一条满足条件的路径。

输出格式

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

样例一

input

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

output

NO
YES

explanation

对于第一个询问，3号点和2号点不连通， 因此答案为“NO”。

对于第二个询问，一条合法的路径是$1\to 3$，路径上的标号形成的字符串为“00”。注意合法路径不唯一。

样例二

input

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

output

NO
YES
YES
NO
YES
YES
YES
YES
YES
NO

限制与约定

对于30%的数据，$1\le m\le 10000$；

对于70%的数据，$1\le n\le 3000,1\le m\le 50000$；

对于100%的数据，$1\le n\le 5000,1\le m\le 500000,1\le q\le 100000$，不存在自环或者重边。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载

题解

https://matthew99.blog.uoj.ac/blog/4968