← 返回题目列表

Codeforces · 27/D

D. 环路2

中文机器翻译题面 查看原题

众所周知,Berland有n个城市,形成银环——城市i和i+1(1≤i<n)以及城市n和1由一条道路连接。政府决定修建m条新道路。准备修建道路清单。每条道路将连接两个城市。每条道路都应该是位于环内或环外的曲线。新道路将与环路没有公共点(道路端点除外)。

现在,施工计划的设计者想知道是否可以以不两条道路相交的方式建造道路(注意,道路可能在端点相交)。如果可以的话,哪些道路应该在环内,哪些道路应该在环外?

输入

第一行包含两个整数 n 和 m (4 ≤ n ≤ 100, 1 ≤ m ≤ 100)。以下 m 行中的每一行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。列表中的任何两个城市都不会由多于一条的道路连接。该列表将不包含银环中存在的道路。

输出

如果不可能以不两条道路相交的方式修建道路,则输出不可能。否则打印 m 个字符。如果道路应在环内,则第 i 个字符应为 i;如果道路应在环外,则第 i 个字符应为 o。如果有多个解,输出任意一个。

示例

输入 #1

4 2
1 3
2 4

输出 #1

io

输入 #2

6 3
1 3
3 5
5 1

输出 #2

ooo