Is there such a street piece

graph hash table estimation maps and navigation

You are given a street graph: intersections are numbered from 0 to n − 1, and stretches of street join pairs of intersections (a stretch can be driven both ways; there are also parallel stretches between the same intersections). For each question “is there a stretch between intersections u and v”, answer YES or NO.

The second and third tests are the streets of central Almaty from OpenStreetMap: 7909 intersections and 10,423 stretches. In the last tests there are 200,000 intersections: estimate how much memory an adjacency matrix would take.

Input

The first line holds n, m and q (1 ≤ n ≤ 2·10⁵, 0 ≤ m, q ≤ 2·10⁵). Then come m lines with the ends of the stretches and q lines with the questions, two intersection numbers each.

Output

For each question, YES or NO.

Examples

Example 1

Input

Output

YES
YES
NO
NO
YES

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 5 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

An adjacency matrix answers such a question with one access. How much will it take with n = 2·10⁵ if a cell is one byte? And if it is one bit?

2The idea

The matrix is 4·10¹⁰ cells: 40 gigabytes in bytes and 5 gigabytes in bits, while there are only 2·10⁵ edges. It is enough to keep the edges themselves, the pairs (u, v) with the smaller end first, in a hash set. A question is also an ordered pair and a lookup in the set.

3Walkthrough

The order of the ends matters: the stretch 3–7 must be found by the question “7 3” too. It is convenient to make the key a single number: the smaller end shifted 20 bits left plus the larger one (the numbers are less than 2²⁰). A second good way is sorted adjacency lists and a binary search in the list of the smaller vertex: O(log deg) per question and no hashing.

The question “is there a stretch from an intersection to itself” is legitimate, and the answer is NO: the graph has no loops.

3+Solution

4Complexity

O(m) memory and O(m + q) time on average. With sorted lists, O(m log m) to build and O(log deg) per question.

5Common mistakes

A matrix. For Almaty it fits (62 MB in bytes), for 2·10⁵ vertices it does not.
A pair in one order. The edge 3–7 written as (3, 7) will not be found by the question (7, 3) unless the ends are ordered.
Looking at all the edges for each question. O(m·q) = 4·10¹⁰.

Algorithms behind it

GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.

neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists

2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems