IMPA/p12356/p12356.cpp

#include <algorithm>
#include <array>
#include <climits>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <queue>

#define rep(i, a, b) for(int i = (a); i < int(b); ++i)
#define repto(i, b) rep(i, 0, b)
#define trav(it, v) for(typeof((v).begin()) it = (v).begin();   \
                it != (v).end(); ++it)

using namespace std;

typedef unsigned int nat;

class Warrior
{
public:
    Warrior() : left{this-1}, right{this+1} {}

    Warrior *left;
    Warrior *right;
    string id;
};

int main()
{
    nat num_soldiers, num_bombs;

    Warrior sentinel;
    sentinel.id = "*";

    while(true)
    {
        cin >> num_soldiers >> num_bombs;
        if(!num_soldiers)
            break;

        vector<Warrior> front_line(num_soldiers);
        repto(i, num_soldiers)
        {
            front_line[i].id = to_string(i+1);
        }

        front_line.front().left = &sentinel;
        front_line.back().right = &sentinel;

        repto(i, num_bombs)
        {
            nat l, r;
            cin >> l >> r;
            front_line[l-1].left->right = front_line[r-1].right;
            front_line[r-1].right->left = front_line[l-1].left;
            cout << front_line[l-1].left->id << " " << front_line[r-1].right->id << endl;
        }
        cout << "-" << endl;

    }

    return 0;
}