CF27D Ring Road 2

题目描述

众所周知，Berland 有 $n$ 个城市，这些城市构成了一个银色环——第 $i$ 个城市和第 $i+1$ 个城市（$1 \leq i < n$）之间有一条道路，第 $n$ 个城市和第 $1$ 个城市之间也有一条道路。政府决定修建 $m$ 条新道路，新道路的列表已经拟定。每条新道路都连接两个城市，每条道路应该是一条曲线，位于环的内部或外部，并且新道路除了端点外不得与银色环有任何公共点。

现在，设计施工方案的工程师们想知道，是否可以在不让任意两条新道路相交的情况下修建这些道路（注意：在道路的端点处可以相交）。如果可以修建，请指出哪些道路应建在环的内部，哪些应建在环的外部。

输入格式

第一行包含两个整数 $n$ 和 $m$（$4 \leq n \leq 100, 1 \leq m \leq 100$）。接下来的 $m$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n, a_i \neq b_i$）。列表中不会有两个城市被多条道路连接，也不会包含已经存在于银色环中的道路。

输出格式

如果无法修建这些道路使得任意两条道路不相交，则输出 Impossible。否则输出 $m$ 个字符，第 $i$ 个字符为 i，表示第 $i$ 条道路应建在环的内部；为 o，表示应建在环的外部。如果有多组解，输出任意一组即可。

输入输出样例 #1

输入 #1

4 2
1 3
2 4

输出 #1

io

输入输出样例 #2

输入 #2

6 3
1 3
3 5
5 1

输出 #2

ooo

说明/提示

由 ChatGPT 5 翻译