Sau khi khám phá \(n\) hành tinh được đánh số từ \(0\) đến \(n-1\), các Pharaoh bắt đầu xây dựng một hệ thống giao thông giữa chúng bằng các đường dịch chuyển một chiều. Mỗi đường dịch chuyển có một hành tinh xuất phát và một hành tinh đích. Khi một du khách sử dụng đường dịch chuyển tại hành tinh xuất phát, họ được dịch chuyển đến hành tinh đích. Hành tinh xuất phát và hành tinh đích có thể trùng nhau. Đường dịch chuyển có hành tinh xuất phát \(u\) và hành tinh đích \(v\) được ký hiệu là \((u,v)\).

Để khuyến khích việc sử dụng rộng rãi hệ thống dịch chuyển, các Pharaoh tạo ra một trò chơi cho du khách trong khi di chuyển. Du khách có thể bắt đầu trò chơi từ bất kỳ hành tinh nào. Các hành tinh \(0,1,\ldots,k-1\) (\(k\le n\)) được gọi là hành tinh đặc biệt. Mỗi lần đi vào một hành tinh đặc biệt, du khách nhận được một con tem.

Ban đầu, với mỗi \(i\) (\(0\le i\le k-2\)), tồn tại một đường dịch chuyển \((i,i+1)\). Các đường dịch chuyển này, có tổng cộng \(k-1\) đường, được gọi là đường dịch chuyển ban đầu.

Các đường dịch chuyển mới được thêm lần lượt từng đường một. Khi các đường mới được thêm vào, du khách có thể bắt đầu nhận được vô hạn tem. Cụ thể, điều này xảy ra khi tồn tại một dãy các hành tinh \(w[0],w[1],\ldots,w[t]\) thỏa mãn:

• \(1\le t\).
• \(0\le w[0]\le k-1\).
• \(w[t]=w[0]\).
• Với mỗi \(i\) (\(0\le i\le t-1\)), tồn tại đường dịch chuyển \((w[i],w[i+1])\).

Du khách được phép sử dụng các đường dịch chuyển ban đầu và mọi đường dịch chuyển đã được thêm cho đến thời điểm hiện tại.

Hãy giúp các Pharaoh xác định, sau mỗi lần thêm một đường dịch chuyển, liệu du khách có thể nhận được vô hạn tem hay không.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

void init(int n, int k);
int add_teleporter(int u, int v);

Hàm init:

• n: số hành tinh.
• k: số hành tinh đặc biệt.
• Hàm được gọi đúng một lần, trước mọi lời gọi add_teleporter.

Hàm add_teleporter:

• u, v: hành tinh xuất phát và hành tinh đích của đường dịch chuyển vừa được thêm.
• Hàm được gọi không quá \(m\) lần.
• Hàm phải trả về \(1\) nếu sau khi thêm đường dịch chuyển \((u,v)\), du khách có thể nhận được vô hạn tem; ngược lại, hàm phải trả về \(0\).
• Ngay khi hàm trả về \(1\), chương trình của bạn sẽ bị dừng.

Ràng buộc

• \(1\le n\le300\,000\).
• \(1\le m\le500\,000\).
• \(1\le k\le n\).

Trong mỗi lần gọi add_teleporter:

• \(0\le u\le n-1\) và \(0\le v\le n-1\).
• Trước khi thêm \((u,v)\), chưa có đường dịch chuyển nào từ hành tinh \(u\) đến hành tinh \(v\).

Phân nhóm

1. (\(2\) điểm) \(n=k\), \(n\le100\), \(m\le300\).
2. (\(10\) điểm) \(n\le100\), \(m\le300\).
3. (\(18\) điểm) \(n\le1\,000\), \(m\le5\,000\).
4. (\(30\) điểm) \(n\le30\,000\), \(m\le50\,000\), \(k\le1\,000\).
5. (\(40\) điểm) Không có ràng buộc bổ sung.

Ví dụ

init(6, 3);

init(4, 2);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(n\ m\ k\).
• Dòng \(2+i\) (\(0\le i\le m-1\)): \(u[i]\ v[i]\).

Đầu tiên, trình chấm mẫu gọi init(n, k). Sau đó, với \(i=0,1,\ldots,m-1\) theo đúng thứ tự, trình chấm gọi add_teleporter(u[i], v[i]).

Trình chấm mẫu in chỉ số của lời gọi add_teleporter đầu tiên trả về \(1\) (một số từ \(0\) đến \(m-1\)), hoặc in \(m\) nếu tất cả các lời gọi đều trả về \(0\). Nếu một lời gọi trả về số nguyên khác \(0\) và \(1\), trình chấm mẫu in \(-1\) rồi dừng chương trình ngay lập tức.

Các tệp ví dụ chính thức dành cho trình chấm mẫu là:

6 5 3
3 4
5 0
4 5
5 3
1 4

4

4 1 2
1 1

0

4 3 2
1 3
2 0
3 2

2

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Game.