BRT 乘客上下车方案

题目描述

小 T 的城市刚刚开始推行 BRT（Bus Rapid Transit），其实就是一种公交车。

BRT 有 $N$ 个站台，分别编号为 $1\sim N$，按照列车通过的顺序递增排列。在列车到站时，会有一些乘客上车，也会有一些乘客下车。

由于 BRT 内空间狭小，乘客完全无法走动，在车上只有靠近车门的乘客才能够下车。和大部分公交车一样，BRT 有两个车门：前门和后门。每一个上车的乘客可以选择从前门或者后门上车。

现在有 $M$ 个乘客，编号为 $1\sim M$，每个人都有各自的起点和终点。你需要安排一种上下车方案，使得每个乘客都能够在自己的终点下车。

若不存在合法方案，请输出 0。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $s_i,t_i$，表示编号为 $i$ 的乘客在第 $s_i$ 个站台上车，在第 $t_i$ 个站台下车。

输出格式

若不存在合法方案，输出一行：

0

否则输出你的方案，共 $2M$ 行，每行输出一种操作。

操作格式如下：

• 1 X 表示编号为 $X$ 的乘客从前门上车；
• 2 X 表示编号为 $X$ 的乘客从后门上车；
• 3 X 表示编号为 $X$ 的乘客下车。

你的输出必须满足：

• 每名乘客必须恰好上车一次、下车一次；
• 乘客只能在自己的起点上车；
• 乘客只能在自己的终点下车；
• 操作顺序必须符合站台经过顺序，不能从编号较大的站台回到编号较小的站台；
• 任意乘客下车时，必须位于车厢的前门端或后门端。

如果存在多种合法方案，输出任意一种即可。

数据范围

本测试数据满足：

并且：

样例

输入

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

样例说明

一种可行过程如下：乘客可以从前门或后门上车；下车时只要该乘客位于车厢某一端，即可从对应车门下车。样例输出只是其中一种合法方案。