Một phiên bản rất sớm và khá tinh vi của chiếc dù ngày nay được mô tả trong cuốn Codex Atlanticus của Leonardo, khoảng năm \(1485\). Dù của ông gồm vải lanh kín được căng bằng một khung gỗ hình kim tự tháp. Hơn \(500\) năm sau, vận động viên nhảy dù Adrian Nicholas thử nghiệm thiết kế này, dùng một kết cấu nhẹ hiện đại để gắn dù với cơ thể.

Chúng ta muốn dùng các vòng móc nối với nhau, đồng thời làm móc cho tấm vải lanh. Mỗi vòng được làm bằng vật liệu bền và dễ uốn, có thể mở ra rồi đóng lại nên dễ dàng móc nối với các vòng khác. Một cấu hình đặc biệt là chuỗi: một dãy vòng mà mỗi vòng chỉ nối với các vòng láng giềng của nó trong dãy, nhiều nhất là hai vòng. Dãy phải có đầu và cuối, mỗi vòng ở đầu hoặc cuối nối với nhiều nhất một vòng khác. Một vòng đơn lẻ cũng là một chuỗi.

Một vòng có thể nối với ba hoặc nhiều vòng khác, nên còn có những cấu hình khác. Một vòng được gọi là then chốt nếu sau khi mở và loại bỏ nó, tất cả các vòng còn lại tạo thành một tập các chuỗi, hoặc không còn vòng nào. Nói cách khác, sau khi loại bỏ vòng đó chỉ được còn lại các chuỗi.

Yêu cầu và giao diện

Hãy đếm số vòng then chốt trong cấu hình được truyền cho chương trình. Ban đầu các vòng rời nhau; sau đó chúng được móc nối dần. Tại bất kỳ thời điểm nào, chương trình có thể được yêu cầu trả về số vòng then chốt trong cấu hình hiện tại. Bạn phải cài đặt ba chương trình con:

• Init(N): được gọi đúng một lần lúc bắt đầu, cho biết cấu hình ban đầu có \(N\) vòng rời nhau, đánh số từ \(0\) đến \(N-1\).
• Link(A, B): móc nối hai vòng \(A\) và \(B\). Bảo đảm \(A \ne B\) và hai vòng chưa được nối trực tiếp với nhau. Ngoài ra không có điều kiện bổ sung nào, kể cả điều kiện xuất phát từ các ràng buộc vật lý. Link(A, B) và Link(B, A) tương đương nhau.
• CountCritical(): trả về số vòng then chốt trong cấu hình hiện tại.

Chi tiết cài đặt

Nộp đúng một tệp rings.c, rings.cpp hoặc rings.pas, cài đặt các chương trình con với chữ ký sau.

C/C++

void Init(int N);
void Link(int A, int B);
int CountCritical();

Pascal

procedure Init(N : LongInt);
procedure Link(A, B : LongInt);
function CountCritical() : LongInt;

Các chương trình con phải hoạt động như đã mô tả. Bạn có thể cài đặt thêm các chương trình con dùng nội bộ. Bài nộp không được giao tiếp dưới bất kỳ hình thức nào với đầu vào/đầu ra chuẩn hoặc với bất kỳ tệp nào khác.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): N L.
• Mỗi dòng từ \(2\) đến \(L+1\): số -1 để gọi CountCritical(), hoặc hai số A B làm tham số cho Link(A, B).

Dữ liệu ra

Trình chấm mẫu in tất cả các kết quả do CountCritical() trả về.

Ràng buộc

Các vòng được đánh số từ \(0\) đến \(N-1\); mỗi lần gọi Link dùng hai số vòng khác nhau và chưa nối trực tiếp. Giới hạn số vòng và số lần gọi trong từng phân nhóm được cho đầy đủ dưới đây.

Phân nhóm

Ví dụ

7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1

7
7
7
7
4
3
2