2586. Take a party

单点时限: 5.0 sec

内存限制: 256 MB

In East China Normal University, there will hold many party in each year. So many students take part in them to recognize more new friends.

As we all know, if A is B’s friend, and B is C’s friend, so we recognize A is C’s friend. Now we were given the relations of the students, what you will do are tell the relations of the students.

输入格式

The first line contains three integer S,M, N(1<=S,M,N<=1000000),S is the number of students who take part in the party. M is the number of relations,N is the number of query.

The next M line, each line contains two integer A,B(1<=A,B<=M),represent A is B’s friend, also B is A’s friend.

Then N line come, are N queries, each line contains two integer a, b( 1<=a, b<=M).

输出格式

About each query,if a is b’s friend output 1,otherwise output 0.

样例

Input
6 4 2
1 2
2 3
3 4
6 5
1 4
2 6
Output
1
0
Hint:
The sample above there are 6 students and 2 queries,1 and 2 are friends, 2 and 3 are friends, 3 and 4 are friends, 6 and 5 are friends,so 1 and 4 are friends,but 2 and 6 are not.

65 人解决,100 人已尝试。

135 份提交通过,共有 415 份提交。

4.2 EMB 奖励。

创建: 11 年,10 月前.

修改: 3 年,6 月前.

最后提交: 3 月,2 周前.

来源: partychen

题目标签
dsu