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 \leq 1000~, ~M \leq 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.

Input

Dòng đầu ghi ba số nguyên dương ~N~, ~M~ và ~K~ ~(K \leq 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.

Sample Input

5 5 2
1 5
1 2
1 2
2 3
2 4
2 5
3 4

Sample Output

1
0