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;
}
#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;
}