#2148. Brt

题目描述

小T的城市刚刚开始推行BRT（Bus Rapid Transit），其实，就是一种公交车。 BRT有N个站台，分别编号为1到N，

按照列车通过的顺序递增排列。在列车到站时，会有一些乘客上车，也会有一些乘客下车。由于BRT内空间狭小，

乘客完全无法走动，在车上只有靠近车门的乘客才能够下车。和大部分公交车一样，BRT有2个车门----前门和后门

。每一个上车的乘客可以选择从前门或者后门上车。现在有M个乘客，编号为1到M，每个人都有各自的起点和终点

，现在，需要聪明的你来安排一种上下车的方案，使得每个乘客都能够在各自的终点下车。

输入格式

第一行是两个整数N,M。

下面依次有M行，每行有两个整数，表示一个乘客的起点和终点。

输出格式

输出你的方案：

1 X 编号为X的乘客从前门上车

2 X 编号为X的乘客从后门上车

3 X 编号为X的乘客下车输出包括2M行

每行一种操作

样例

样例输入

5 7  

1 3  

1 2  

2 3  

2 4  

4 5  

3 5  

3 5

样例输出

1 1  

1 2  

3 2  

2 4  

1 3  

3 3  

3 1  

1 7  

1 6  

3 4  

1 5  

3 7  

3 6  

3 5  

数据范围与提示

请不要提交！