Truy Vấn Đường Mới

Byteland có $n$ thành phố và ban đầu không có đường nào. Mỗi ngày, một con đường mới được xây dựng nối hai thành phố. Sau $m$ ngày, tất cả $m$ con đường đã được xây dựng.

Trả lời $q$ truy vấn: mỗi truy vấn hỏi ngày nào là ngày đầu tiên mà hai thành phố $a$ và $b$ trở nên liên thông. Nếu chúng không bao giờ liên thông, in $-1$.

Dữ liệu vào

• Dòng 1: ba số nguyên $n$, $m$, $q$.
• $m$ dòng tiếp theo: mỗi dòng hai số nguyên $a$, $b$ — con đường xây dựng vào ngày đó.
• $q$ dòng tiếp theo: mỗi dòng hai số nguyên $a$, $b$ — truy vấn.

Dữ liệu ra

• $q$ dòng — mỗi dòng là số ngày đầu tiên hai thành phố liên thông, hoặc $-1$.

Ràng buộc

• $1\le n,m,q\le 2\times {10}^5$
• $1\le a,b\le n$

Ví dụ