Henry và Hetty được giao thiết kế một bộ định tuyến gồm:

• \(N\) nút vào, đánh số từ \(1\) đến \(N\).
• \(N\) nút ra, đánh số từ \(N+1\) đến \(2N\).
• Một số nút trung gian, được đánh số tiếp theo.
• Các kết nối có hướng giữa những cặp nút khác nhau.

Nút \(X\) có thể truyền dữ liệu đến nút \(Y\) nếu \(X=Y\), hoặc nếu dữ liệu có thể truyền từ \(X\) đến một nút \(Z\) và có kết nối trực tiếp từ \(Z\) đến \(Y\).

Bộ định tuyến hợp lệ phải thỏa mãn tất cả các điều kiện sau:

• Mỗi nút vào truyền được dữ liệu đến mọi nút ra.
• Mỗi nút vào chỉ nhận được dữ liệu từ chính nó.
• Mỗi nút ra chỉ truyền được dữ liệu đến chính nó.
• Nếu \(X\ne Y\) và \(X\) truyền được dữ liệu đến \(Y\), thì \(Y\) không truyền được dữ liệu ngược lại đến \(X\).
• Với mọi cặp nút \(X\ne Y\) mà \(X\) truyền được dữ liệu đến \(Y\), chỉ có duy nhất một đường đi có hướng từ \(X\) đến \(Y\).
• Tổng số nút không vượt quá \(500\,000\).
• Số kết nối không vượt quá giới hạn \(M_{\text{lim}}\).
• Công suất lớn nhất không vượt quá giới hạn \(P_{\text{lim}}\).

Với mỗi nút \(X\), đặt \(IN_X\) là số nút vào có thể truyền dữ liệu đến \(X\) và \(OUT_X\) là số nút ra có thể nhận dữ liệu từ \(X\). Công suất của \(X\) là \(P_X=IN_X\cdot OUT_X\). Công suất lớn nhất của bộ định tuyến là giá trị lớn nhất của \(P_X\) trên mọi nút.

Dữ liệu vào

Bạn không cần viết chương trình giải bài toán. Hệ thống cung cấp các tệp 0-router.in, 1-router.in, ..., 7-router.in. Mỗi tệp gồm ba số nguyên \(N\), \(M_{\text{lim}}\), \(P_{\text{lim}}\).

Dữ liệu ra

Nộp một tệp ZIP chứa thư mục router-out. Với mỗi tệp đầu vào có chỉ số \(i\), thư mục phải chứa i-router.out.

Mỗi tệp đầu ra gồm:

• Dòng đầu chứa hai số nguyên \(N_{\text{tot}}\) và \(M\): tổng số nút và số kết nối.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X,Y\), biểu diễn kết nối có hướng từ \(X\) đến \(Y\).

Các nút vào là \(1,\ldots,N\), các nút ra là \(N+1,\ldots,2N\), và các nút còn lại là nút trung gian. Mọi số hiệu nút phải nằm trong đoạn \([1,N_{\text{tot}}]\).

Phân nhóm

• Tệp kiểm thử 1: \(N=118\), \(M_{\text{lim}}=1\,000\,000\), \(P_{\text{lim}}=1\,000\,000\), chiếm \(4\%\) số điểm.
• Tệp kiểm thử 2: \(N=223\), \(M_{\text{lim}}=1\,000\,000\), \(P_{\text{lim}}=1\,000\,000\), chiếm \(5\%\) số điểm.
• Tệp kiểm thử 3: \(N=1250\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(6\%\) số điểm.
• Tệp kiểm thử 4: \(N=5101\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(6\%\) số điểm.
• Tệp kiểm thử 5: \(N=9934\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(26\%\) số điểm.
• Tệp kiểm thử 6: \(N=9955\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=100\,000\), chiếm \(30\%\) số điểm.
• Tệp kiểm thử 7: \(N=9978\), \(M_{\text{lim}}=100\,000\), \(P_{\text{lim}}=100\,000\), chiếm \(23\%\) số điểm.

Tệp kiểm thử 0 là ví dụ và không tính điểm.

Ví dụ

Với đầu vào 3 100 200, một bộ định tuyến hợp lệ có thể gồm \(9\) nút và \(8\) kết nối:

9 8
1 7
2 7
3 8
7 8
8 4
8 9
9 5
9 6

Nút 8 nhận dữ liệu từ ba nút vào và truyền đến ba nút ra, nên công suất của nút này là \(3\cdot3=9\). Có thể có nhiều bộ định tuyến hợp lệ cho cùng một bộ giới hạn.

Nguồn

CEOI 2016, ngày 2, bài 3.