**67 人解决**，102 人已尝试。

**139 份提交通过**，共有 429 份提交。

**4.2** EMB 奖励。

**单点时限: **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.