You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

想买一台手机。

Description

他去了好几个专卖店，其中有几个专卖店之间有路，有几个则没有。现给出几条路径，再给出几组数$ai,bi$，求$a$与$b$间有没有路。

Input

第一行三个数字$x,y,z$，代表店数、路径数、询问数。 接下来$y$行，每行两个数字$a,b$，代表$a,b$之间互通（双向皆可）。 接下来$z$行，每行两个数$a,b$，询问$a,b$之间是否互通。

Output

$z$行，每行一个数，代表对应的两个专卖店互通为$1$，不互通则是$0$

Samples

3 2 1
1 2
1 3
2 3

0

3 2 2
1 2
1 3
1 3
2 3

1
0

Limitation

$2 \le x,y \le 10^4$
$1 \le z \le 10^4$