Giải bài trực tuyến

Thỏ và sói chơi một trò chơi đuổi bắt như sau:

Trên một đồ thị vô hướng gồm N nút và M cạnh (N ≤ 1000, M ≤ 10000), tại thời điểm bắt đầu, sói và thỏ mỗi người đứng ở một nút khác nhau. Giả thiết các cạnh của đồ thị đều có cùng một độ dài và vận tốc của sói và thỏ là bằng nhau: Sau mỗi một đơn vị thời gian, sói (thỏ) đều có thể hoặc đứng tại chỗ hoặc chạy sang một nút liền kề (có cạnh nối trực tiếp). Trong trò chơi này, sói sẽ cố gắng đuổi để bắt thỏ và thỏ tất nhiên sẽ phải cố gắng chạy sao cho không bị bắt. Thỏ có chút lợi thế là thấy được sói sẽ chạy về hướng nào (nút kế tiếp hoặc đứng yên) rồi mới phải quyết định hướng chạy của mình. Mặc dù vậy, cả hai cũng sẽ cùng đến nút mới sau một đơn vị thời gian, nghĩa là nếu sói và thỏ nhảy đến cùng một nút thì sói sẽ bắt được thỏ.

Bài toán đặt ra là với mỗi trạng thái ban đầu, gồm vị trí của thỏ và sói, hãy cho biết sói có thể chắc chắn bắt được thỏ hay không. Nói cách khác, liệu có chiến lược cho sói để bắt được thỏ trong hữu hạn thời gian, không phụ thuộc vào chiến lược của thỏ hay không.

Lưu ý : các bạn có thắc mắc gì về test xin liên hệ mr_invincible ^^

Input

Dữ liệu nhập theo khuôn dạng như sau:

Dòng đầu ghi ba số nguyên dương N, M và K (K ≤ 10).

K dòng tiếp theo, mỗi dòng ghi hai số, là vị trí ban đầu của sói và thỏ.

M dòng tiếp theo mô tả các cạnh của đồ thị, mỗi dòng ghi hai số là hai nút đầu mút của một cạnh.

Output

Ghi kết quả gồm K dòng, lần lượt là câu trả lời cho các trạng thái ban đầu theo thứ tự như trong file input. Trên mỗi dòng, ghi 1 nếu có chiến lược sói chắc chắn bắt được thỏ và 0 trong trường hợp ngược lại.

Example

Input:
5 5 2
1 5
1 2
1 2
2 3
2 4
2 5
3 4


Output:
1
0