Có một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Đồ thị không chứa khuyên hay cạnh bội và không nhất thiết liên thông. Các đỉnh được đánh số từ $1$ đến $n$.
Có $q$ truy vấn. Mỗi truy vấn là một cặp $(x, y)$. Bạn cần xác định xem khoảng cách giữa $x$ và $y$ có lớn hơn nghiêm ngặt $20\,000$ hay không.
Khoảng cách giữa hai đỉnh là số lượng cạnh trên đường đi ngắn nhất giữa chúng. Nếu không có đường đi ngắn nhất, khoảng cách được coi là $+\infty > 20\,000$.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $q$ ($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$).
Tiếp theo là $m$ dòng, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$, biểu diễn các cạnh ($1 \le u_i < v_i \le n$, không có hai cạnh nào trùng nhau).
Sau đó là $q$ dòng, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$ ($1 \le x_i, y_i \le n$, $x_i$ và $y_i$ có thể trùng nhau).
Kết quả
In ra $q$ dòng, mỗi dòng là "YES" hoặc "NO": câu trả lời cho các truy vấn.
Ví dụ
Dữ liệu vào mẫu 1
10 5 10 1 2 1 7 3 10 4 10 5 6 3 3 5 6 5 2 10 6 9 4 6 6 1 7 10 1 10 5 8 7
Kết quả mẫu 1
NO NO YES YES YES NO NO YES YES YES
Ghi chú
Trong ví dụ, chỉ có $10$ đỉnh trong đồ thị, vì vậy thực chất chúng ta đang kiểm tra xem các đỉnh có nằm ở các thành phần liên thông khác nhau hay không.