#2148. Brt

内存限制:259 MiB 时间限制:10 Sec

题目描述

小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

数据范围与提示

请不要提交!