Truy Vấn Đường Mới

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq n, m, q \leq 2 \times 10^{5}$
$1 \leq a, b \leq n$

Ví dụ

Input	Output	Giải thích
5 4 3 1 2 2 3 1 3 2 5 1 3 3 4 3 5	2 -1 4	Ngày 2 nối 2-3, hoàn thiện đường 1-3. Thành phố 4 không bao giờ liên thông.
3 2 2 1 2 2 3 1 3 2 2	2 0	Truy vấn (2,2): thành phố liên thông với chính nó từ ngày 0.

Bình luận

Không có bình luận tại thời điểm này.