I am applying the exact same solution as proposed in the tutorial, though using bfs instead of dfs.


#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<sstream>
#include<deque>
#include<math.h>
#include<cstring>
#include <bitset>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>

#define all(v) v.begin(),v.end()
#define mpair make_pair

using namespace std;
typedef long double ld;
const ld epsilon = 1e-9;
typedef long long ll;
vector<pair<int, int> > roads;
bool intersect(int i, int j)
{
        int a = (roads[i].first - roads[j].first) * (roads[i].second - roads[j].first);
        int b = (roads[i].first - roads[j].second) * (roads[i].second - roads[j].second);
        int c = (roads[j].first - roads[i].first) * (roads[j].second - roads[i].first);
        int d = (roads[j].first - roads[i].second) * (roads[j].second - roads[i].second);
        if(a == 0 || b == 0 || c == 0 || d == 0)
                return false;
        if((a < 0) ^ (b < 0))
                return true;
        if((c < 0) ^ (d < 0))
                return true;
}
int main()
{
        //freopen("bobi.in", "r", stdin);
        int n, m;
        cin >> n >> m;
        vector<int> vis(m, -1);
        roads.resize(m);
        for(int i = 0; i < m; i++)
                cin >> roads[i].first >> roads[i].second;

        queue<int> toProcess;
        int cur;
        for(int i = 0; i < m; i++)
        {
                if(vis[i] == -1)
                {

                        toProcess.push(i);
                        vis[i] = 0;
                        while(!toProcess.empty())
                        {
                                cur= toProcess.front();
                                toProcess.pop();
                                for(int j = 0; j < m; j++)
                                {
                                        if(j == cur)
                                                continue;
                                        if(intersect(cur, j))
                                        {
                                                if(vis[j] != -1)
                                                {
                                                        if(vis[j] == vis[cur])
                                                        {
                                                                cout << "Impossible" << endl;
                                                                return 0;
                                                        }
                                                }
                                                else
                                                {
                                                        vis[j] = !vis[cur];
                                                        toProcess.push(j);
                                                }
                                        }
                                }
                        }
                }
        }
        for(int i = 0; i < m; i++)
                if(vis[i] == 0)
                        cout << "i";
                else
                        cout << "o";
        cout << endl;
        return 0;
}