Ban ra đề đang viết chương trình sinh test cho một bài về đồ thị. Họ cần sinh một đơn đồ thị vô hướng đỉnh cạnh. Thuật toán sinh như sau:
Nếu đã lấy đủ cạnh thì dừng;
Gọi là tập các cặp với và đang không kề với , tức là tập các cạnh chưa có trong đồ thị;
Sắp xếp theo thứ tự từ điển ( đứng trước nếu hoặc là hoặc là và );
Chọn một số tự nhiên trong phạm vi từ đến ;
Nạp cạnh thứ trong vào đồ thị, lặp lại bước .
Cho biết các số được chọn ở bước thứ , hãy giúp ban ra đề in ra các cạnh của đồ thị. Lưu ý, các loại chỉ số trong bài đều được đánh số bắt đầu từ .
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương là số đỉnh và số cạnh của đồ thị;
dòng tiếp theo, dòng thứ chứa một số nguyên dương là số được chọn ở bước thứ của lần lặp thứ .
Dữ liệu ra:
In ra cạnh được chọn theo thứ tự chọn của thuật toán. Với mỗi cạnh, in ra hai đỉnh trên một dòng cách nhau bởi dấu cách, đỉnh bé hơn phải được in trước.