该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

等价命题

时间限制：1000ms

空间限制：256MB

题目描述

最近小杰学习了有关实数完备性定理的7个定理，这7个定理两两等价。如果把这7个命题记作1到7，教材是通过 $1 \implies 2 \implies 3 \implies 4 \implies 5 \implies 6 \implies 7 \implies 1$ 来证明这七个命题是等价的。小杰对于命题之间的推出关系所产生的结构产生了兴趣。

已知命题推出关系有两种性质：

1. 如果 $A \implies B$ 且 $B \implies C$，那么 $A \implies C$。
2. 如果 $A \implies B$ 且 $B \implies A$，那么 $A \Leftrightarrow B$ 也就是A和B等价。

现在小杰手里有n个命题，编号为1到n，已知部分命题之间的推出关系。小杰希望你根据已有信息，帮忙判断两个命题是否一定等价。

输入格式

第一行两个数字n、m和q，分别表示有n个命题、m个推出关系和q次询问。 接下来m行每行两个数A和B，是命题的编号，表示$A \implies B$。 然后q行每行两个数A和B，也是命题的编号，表示询问这两个命题是否等价。

输出格式

输出q个数，第i个数代表第i次询问是否一定等价。其中1代表等价，0代表不能确定。

样例输入1

7 7 3
1 2
2 3
3 4
4 5
5 6
6 7
7 1
1 3
2 5
7 4

样例输出1

1
1
1

样例1解释

明显7个命题两两等价。

样例输入2

8 6 6
1 2
2 3
3 1
1 4
4 1
1 5
1 1
1 2
1 3
1 4
1 5
6 7

样例输出2

1
1
1
1
0
0

数据范围及约定

对于占本体总分 $60\%$ 的数据，$n \leq 20$。

对于所有数据，$n \leq 200, m \leq 2n, q \leq n$，保证命题的编号在1到n之间。