TRANSINFO - Truyền thông tin
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: chandoi

     Mạng máy tính nơi C làm việc gồm có N máy tính, khi nhận được dữ liệu từ máy chủ hay máy khác, máy thứ i sẽ truyền dữ liệu nó nhận được tới một máy khác có giá trị là Ai. Nhận nhiệm vụ truyền dữ liệu từ máy chủ tới N máy tính kia, C nhận ra rằng, nếu cậu ta truyền dữ liệu từ máy chủ tới một máy tính bất kì, thì có thể một số máy tính sẽ không nhận được dữ liệu. Bởi vậy C muốn tăng thêm một số ít nhất các liên kết truyền dữ liệu giữa các máy, để dữ liệu từ máy chủ tới một máy tính bất kì, thì tất cả các máy tính còn lại đều sẽ nhận được dữ liệu.

     Hãy giúp C, xác định một lượng ít nhất các liên kết cần phải thêm đó

Chú ý: Máy u có thể truyền dữ liệu tới máy v nhưng chưa chắc máy v có thể truyền dữ liệu tới máy u. 

INPUT:

      - Một số nguyên N, số máy tính client (1<=N<=105)

      - Dòng 2: Gồm N số nguyên A1...AN (1<=Ai<=N).

OUTPUT:

      - Dòng 1: Số nguyên M, số liên kết cần phải thêm

      - M dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v thể hiện liên kết mới từ u tới v

Nếu có nhiều đáp án, in ra một cách bất kì 

Ví dụ

  • input
    2
    2 2
    output
    1
    2 1
Back to Top