题目描述

本题比较特殊，附件中有本题所有数据，$\operatorname{chk.cpp}$ 和 $\operatorname{testlib.h}$。但是由于输出量较大，应提交一个能在规定时间内读取输入并产生输出的程序。

███ 想给一张图边染色。

给定一个 $n$ 个点 $m$ 条边的无向图（保证 $m$ 是 $3$ 的倍数），你要把这张图的边染成 $\frac{m}{3}$ 种颜色，要求每种颜色出现次数为 3 且同种颜色必须形成一条长度为 3 的路径（允许有重复点）。

███ 知道这是一个 NP 完全问题，所以保证 $n,m$ 在一定范围内且数据随机。

输入格式

第一行输入两个正整数 $n,m$，表示图的点数和边数。

接下来 $m$ 行每行输入两个正整数 $x_i,y_i$，表示存在 $x_i$ 到 $y_i$ 的边。保证无重边和自环。

输出格式

输出 $\frac{m}{3}$ 行，每行四个正整数 $a_i,b_i,c_i,d_i$。表示颜色为 $i$ 的边为 $\{a_i,b_i\},\{b_i,c_i\},\{c_i,d_i\}$。

自然地，你需要保证 $\bigcup_{i=1}^{m}\{\{x_i,y_i\}\} = \bigcup_{i=1}^{\frac{m}{3}}\{\{a_i,b_i\},\{b_i,c_i\},\{c_i,d_i\}\}$

样例一

input

10 15
3 10
10 4
3 6
5 8
10 9
5 2
1 4
1 9
1 7
8 3
1 6
6 10
10 2
8 2
4 3

output

2 5 8 2
8 3 10 2
3 4 1 7
6 1 9 10
3 6 10 4

explanation

限制与约定

样例不在数据中。对于所有数据，保证 $1 \leq x_i \lt y_i \leq n$，给出的边在 $\frac{n (n-1)}{2}$ 中随机取 $m$ 条。

本题有 $10$ 个子任务，每个子任务有 $5$ 个点。只有该任务下测试点全部通过才能得到该子任务的分数。

时间限制： $1\texttt{s}$

空间限制： $1024\texttt{MB}$