Joker trở lại thành phố Gotham để thực hiện một kế hoạch độc ác khác. Thành phố có \(N\) giao lộ, được đánh số từ \(1\) đến \(N\), và \(M\) con đường, được đánh số từ \(1\) đến \(M\). Mỗi con đường nối hai giao lộ khác nhau, và giữa hai giao lộ có nhiều nhất một con đường.

Để thực hiện kế hoạch, Joker cần một số lẻ con đường tạo thành một chu trình. Cụ thể, với một giao lộ \(S\) và một số nguyên dương chẵn \(k\), cần có một dãy giao lộ \(S,s_1,\ldots,s_k,S\) sao cho có đường nối \(S\) với \(s_1\), đường nối \(s_k\) với \(S\), và đường nối \(s_{i-1}\) với \(s_i\) với mọi \(i=2,\ldots,k\).

Tuy nhiên, cảnh sát đang kiểm soát các con đường của Gotham. Vào ngày \(i\), họ giám sát một tập các con đường có số hiệu liên tiếp: tất cả các đường \(j\) thỏa mãn \(l_i\le j\le r_i\). Joker không thể sử dụng những con đường bị giám sát trong kế hoạch của mình. Không may cho cảnh sát, Joker có gián điệp trong Sở Cảnh sát Gotham, nên hắn biết những con đường nào bị giám sát vào từng ngày.

Với một số ngày cho trước, hãy xác định liệu Joker có thể thực hiện kế hoạch vào mỗi ngày hay không. Muốn thực hiện được, vào ngày đó phải tồn tại một chu trình gồm một số lẻ con đường không bị giám sát.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(Q\), lần lượt là số giao lộ, số con đường và số ngày cần xét.

\(M\) dòng tiếp theo mô tả các con đường. Dòng thứ \(j\) (\(1\le j\le M\)) chứa hai số nguyên \(u,v\), cho biết con đường \(j\) nối hai giao lộ \(u\) và \(v\). Hai giao lộ này khác nhau; giữa hai giao lộ có nhiều nhất một con đường.

\(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i,r_i\), cho biết vào ngày \(i\) (\(1\le i\le Q\)), cảnh sát giám sát tất cả các con đường có số hiệu \(j\) thỏa mãn \(l_i\le j\le r_i\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) (\(1\le i\le Q\)) chứa YES nếu Joker có thể thực hiện kế hoạch vào ngày \(i\), hoặc NO nếu không thể.

Ràng buộc

• \(1\le N,M,Q\le200\,000\).
• \(1\le u,v\le N\), \(u\ne v\).
• Giữa hai giao lộ có nhiều nhất một con đường.
• \(1\le l_i\le r_i\le M\) với mọi \(1\le i\le Q\).
• Giới hạn thời gian: \(2{,}0\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(6\) điểm: \(1\le N,M,Q\le200\).
2. \(8\) điểm: \(1\le N,M,Q\le2000\).
3. \(25\) điểm: \(l_i=1\) với mọi \(i=1,\ldots,Q\).
4. \(10\) điểm: \(l_i\le200\) với mọi \(i=1,\ldots,Q\).
5. \(22\) điểm: \(Q\le2000\).
6. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7

NO
YES