{"problem":{"name":"H. Mr. Hamra and his quantum particles","description":{"content":"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 par","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10216H"},"statements":[{"statement_type":"Markdown","content":"Mr. Hamra is preparing a crazy experiment for the next scientific Saturday.\n\nQuantum 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.\n\nMr. 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. \n\nFirst line of the input will be $T$, the number of test cases.\n\nEach test case starts with a line of three numbers, $N, M, Q$ ($1 <= N, M, Q <= 10^5$) the number of particles, quantum entanglement between particles, and the number of questions.\n\neach of the next $M$ lines contain two integers, $u$ and $v$ the particles that are in quantum entanglement.\n\nNext $Q$ lines contain two integers, $X$ and $Y$ the $i_{t h}$ questions.\n\nFor each test case, print a binary string of length $Q$ the $i_{t h}$ char of the string is \"1\" if there is a quantum entanglement between them or \"0\" otherwise (Without the quotes).\n\n## Input\n\nFirst 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 <= N, M, Q <= 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_{t h}$ questions.\n\n## Output\n\nFor each test case, print a binary string of length $Q$ the $i_(t h)$ char of the string is \"1\" if there is a quantum entanglement between them or \"0\" otherwise (Without the quotes).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N, M, Q \\in \\mathbb{Z} $ denote the number of particles, entanglement relations, and queries, respectively.  \n- Let $ G = (V, E) $ be an undirected graph where $ V = \\{1, 2, \\dots, N\\} $ is the set of particles, and $ E \\subseteq V \\times V $ is the set of $ M $ entanglement edges.  \n- The entanglement relation is transitive: if $ (u,v) \\in E $ and $ (v,w) \\in E $, then $ u $ and $ w $ are in the same connected component.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unspecified} $  \n2. For each test case:  \n   - $ 1 \\le N, M, Q \\le 10^5 $  \n   - For each edge $ (u,v) \\in E $: $ 1 \\le u, v \\le N $, $ u \\ne v $  \n   - For each query $ (X,Y) $: $ 1 \\le X, Y \\le N $  \n\n**Objective**  \nFor each test case, compute the connected components of $ G $.  \nFor each query $ (X,Y) $, output:  \n$$\n\\begin{cases}\n\\texttt{\"1\"} & \\text{if } X \\text{ and } Y \\text{ are in the same connected component} \\\\\n\\texttt{\"0\"} & \\text{otherwise}\n\\end{cases}\n$$  \nOutput a binary string of length $ Q $ for each test case.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10216H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}