Bạn là kỹ sư trưởng của một công ty cung cấp điện tại Thành phố Mặt trời, một thành phố hiện đại với ~N~ trạm điện đánh số từ 1 đến ~N~. Thành phố được cấp điện thông qua một mạng lưới điện gồm ~M~ đường dây, mỗi đường dây kết nối hai trạm điện và có thể truyền điện theo cả hai hướng.

Trạm điện chính đặt tại trạm số 1, cung cấp điện cho các trạm điện có kết nối trực tiếp hay gián tiếp đến nó. Những trạm điện không có kết nối trực tiếp hoặc gián tiếp với trạm số 1 sẽ không có điện.

Vì thành phố đang phát triển nên nhu cầu sử dụng điện tăng lên hằng ngày. Để giải quyết được vấn đề đó, công ty quyết định nâng cấp hệ thống đường dây điện. Trong quá trình nâng cấp, lần lượt công ty sẽ thực hiện ~Q~ sự kiện sửa chữa đường dây. Việc sửa chữa này sẽ khiến đường dây tạm dừng hoạt động, và một số trạm điện sẽ bị mất điện.

Công ty của bạn cần biết trạm điện nào sẽ mất điện sau mỗi sự kiện sửa chữa để có thể thông báo mất điện đến cư dân thành phố.

Yêu cầu: Xác định thời điểm trạm điện bị mất điện sau các sự kiện sửa chữa.

Input

• Dòng đầu chứa 3 số nguyên ~N, M, Q~ (~1 \le N \le 10^5, 1 \le M \le 2 \times 10^5, 1 \le Q \le N~).
• ~M~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~A_i, B_i~ (~1 \le i \le M~) thể hiện đường dây nối giữa 2 trạm ~A_i, B_i~ (~1 \le A_i < B_i \le N~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~C_i, D_i~ (~1 \le i \le Q~) thể hiện sự kiện tạm dừng hoạt động đường dây nối giữa 2 trạm ~C_i, D_i~ (~1 \le C_i < D_i \le N~).

Output

• Ghi ra ~N-1~ dòng: Dòng thứ ~i~ cho biết trạm điện thứ ~i+1~ bị mất điện sau sự kiện thứ mấy. Nếu trạm không bị mất điện sau tất cả các sự kiện, ghi -1. Nếu trạm không có điện từ ban đầu, ghi 0.

Sample Input 1

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

Sample Output 1

3
5
4
5
5