405933: GYM102163 H Mr. Hamra and his quantum particles

Mr. Hamra is preparing a crazy experiment for the next scientific Saturday.

Quantum entanglement is a weird relationship that can occur between two particles. And it has the following feature: if particles $$$A$$$ and $$$B$$$ are in quantum entanglement, and $$$B$$$ and $$$C$$$ are in quantum entanglement, then $$$A$$$ and $$$C$$$ are in quantum entanglement too.

Mr. Hamra has $$$N$$$ particles. He knows $$$M$$$ relationship of quantum entanglement between them. For his magical experiment, he will ask you $$$Q$$$ questions, in each question he will give you two particles and ask whether there is a quantum entanglement between them.

First line of the input will be $$$T$$$, the number of test cases.

Each test case starts with a line of three numbers, $$$N, M, Q$$$ ($$$ 1 \le N, M, Q \le 10^5$$$) the number of particles, quantum entanglement between particles, and the number of questions.

each of the next $$$M$$$ lines contain two integers, $$$u$$$ and $$$v$$$ the particles that are in quantum entanglement.

Next $$$Q$$$ lines contain two integers, $$$X$$$ and $$$Y$$$ the $$$i_{th}$$$ questions.

For each test case, print a binary string of length $$$Q$$$ the $$$i_{th}$$$ char of the string is "1" if there is a quantum entanglement between them or "0" otherwise (Without the quotes).

1
3 1 4
1 2
1 2
2 3
3 1
2 2

1001