Let $G = (V, E)$ be a simple undirected graph with $N$ vertices and $M$ edges, where $V = {1, \\dots, N}$. A tuple $angle.l u, v, w angle.r$ is called as boomerang in $G$ if and only if ${(u, v), (v, w)} subset.eq E$ and $u != w$; in other words, a boomerang consists of two edges which share a common vertex.
Given $G$, your task is to find as many disjoint boomerangs as possible in $G$. A set $S$ contains disjoint boomerangs if and only if each edge in $G$ only appears at most once (in one boomerang) in $S$. You may output any valid disjoint boomerangs, but the number of disjoint boomerangs should be maximum.
For example, consider a graph $G = (V, E)$ of $N = 5$ vertices and $M = 7$ edges where $E = {(1, 2)$, $(1, 4)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)}$.
The maximum number of disjoint boomerangs in this example graph is $3$. One example set containing the $3$ disjoint boomerangs is ${angle.l 4, 1, 2 angle.r, angle.l 4, 3, 2 angle.r, angle.l 2, 5, 3 angle.r}$; no set can contain more than $3$ disjoint boomerangs in this example.
Input begins with a line containing two integers: $N$ $M$ ($1 <= N, M <= 100000$), representing the number of vertices and the number edges in $G$, respectively. The next $M$ lines, each contains two integers: $u_i$ $v_i$ ($1 <= u_i < v_i <= N$), representing the edge $(u_i, v_i)$ in $G$. You may safely assume that each edge appears at most once in the given list.
The first line of output contains an integer: $K$, representing the maximum number of disjoint boomerangs in $G$. The next $K$ lines, each contains three integers: $u$ $v$ $w$ (each separated by a single space), representing a boomerang $angle.l u, v, w angle.r$. All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.
## Input
Input begins with a line containing two integers: $N$ $M$ ($1 <= N, M <= 100000$), representing the number of vertices and the number edges in $G$, respectively. The next $M$ lines, each contains two integers: $u_i$ $v_i$ ($1 <= u_i < v_i <= N$), representing the edge $(u_i, v_i)$ in $G$. You may safely assume that each edge appears at most once in the given list.
## Output
The first line of output contains an integer: $K$, representing the maximum number of disjoint boomerangs in $G$. The next $K$ lines, each contains three integers: $u$ $v$ $w$ (each separated by a single space), representing a boomerang $angle.l u, v, w angle.r$. All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.
[samples]
[{"iden":"statement","content":"Monocarp 玩一款名为《Moonbound》的电脑游戏。这个游戏的主要目标是使用物质操纵器——一个非常强大的神器——拯救银河系免受外星势力的入侵。不过，当 Monocarp 不忙于拯救银河系时——事实上，他现在只是在为自己的角色建造一座房子。\n\n现在 Monocarp 需要为房子建造一堵墙。Moonbound 世界的整个结构由方块组成，Monocarp 想要建造的墙也不例外。这堵墙将呈正方形，由 $n$ 行水平排列的方块组成，每行包含 $n$ 个方块（$n$ 为偶数）。我们将第 $i$ 行第 $j$ 列方块的位置记为 ($i$, $j$)。\n\nMonocarp 希望用两种类型的方块建造这堵墙：石砖和沙砖。Monocarp 认为，当不同类型的方块以棋盘样式排列时，墙会显得美观：左上角的方块应为石砖，其右侧的方块应为沙砖，再右侧的方块应为石砖，依此类推；第二行的第一个方块应为沙砖，第二个方块应为石砖，依此类推。形式化地说，若 $i + j$ 能被 $2$ 整除，则位置 ($i$, $j$) 应放置石砖；否则应放置沙砖。\n\n物质操纵器有两种放置方块的模式，但两种模式都对放置方块的位置有特殊要求。我们称一个不包含任何方块的位置 ($i$, $j$) 为 _空闲_，当且仅当它位于边界上（$i = 1$、$i = n$、$j = 1$ 或 $j = n$），或与至少一个已包含方块的位置相邻（共享一条边）。\n\n方块可以通过两种模式放置：要么选择任意一个 _空闲_ 位置，并在其中放置一个选定类型的方块；要么选择一个 $2 \\times 2$ 的正方形区域，该区域至少包含一个 _空闲_ 位置，并将该正方形内所有 _空闲_ 位置都填充为 _相同_ 类型的选定方块。\n\nMonocarp 希望使用物质操纵器在不超过 $\\frac{3n^2}{4}$ 次操作内完成墙体建造。如果他在本应放置其他类型方块的位置放置了错误类型的方块，他将不得不拆除墙体的一部分，这将耗费大量时间——因此 Monocarp 不会执行任何在错误位置放置方块的操作。请帮他制定一个操作计划！\n\n输入仅包含一个 _偶数_ 整数 $n$（$2 \\leq n \\leq 50$）——墙的行数（也是每行的方块数）。"},{"iden":"input","content":"输入仅包含一个 _偶数_ 整数 $n$（$2 \\leq n \\leq 50$）——墙的行数（也是每行的方块数）。"},{"iden":"output","content":"第一行输出 $k$（$1 \\leq k \\leq \\frac{3n^2}{4}$）——建造墙体所需的物质操纵器操作次数。接下来 $k$ 行，每行描述一个操作，格式为四个整数 $t$ $x$ $y$ $b$：\n\n$t$ 表示操作类型：若为 $1$，表示仅填充一个位置；若为 $2$，表示填充一个 $2 \\times 2$ 的正方形区域；\n$x$ $y$ 是 Monocarp 填充的位置坐标。若操作类型为 $1$，则位置 ($x$, $y$) 将被填充——且在操作前该位置必须是 _空闲_ 的；若操作类型为 $2$，则位置 ($x$, $y$)、($x$, $y + 1$)、($x + 1$, $y$) 和 ($x + 1$, $y + 1$) 将被填充——且其中至少有一个位置在操作前是 _空闲_ 的；\n$b$ 表示所有空闲位置将被填充的方块类型（$1$ 表示石砖，$2$ 表示沙砖）。\n\n任何操作都不能导致某个位置出现不属于该位置的方块。当填充 $2 \\times 2$ 正方形时，该正方形内不能有任何位置超出墙体边界（因此若 $t = 2$，则 $1 \\leq x, y \\leq n - 1$）。\n\n若存在多个满足 $k \\leq \\frac{3n^2}{4}$ 的可行方案，请输出其中任意一个。注意，不同类型的方块必须按棋盘样式排列，且位置 ($1$, $1$) 必须为石砖。"},{"iden":"note","content":"第一个示例中的操作序列（白色代表空位置，深灰代表石砖，浅灰代表沙砖）： "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be even, $ 2 \leq n \leq 50 $.
The wall is an $ n \times n $ grid.
For position $ (i, j) $, the target block type is:
- Stone if $ i + j \equiv 0 \pmod{2} $,
- Sand if $ i + j \equiv 1 \pmod{2} $.
**Constraints**
- Initial grid: all positions empty.
- Two allowed operations:
1. **Type 1**: Place a single block of correct type on a *free* position.
- A position is *free* if it is on the border ($ i=1 $, $ i=n $, $ j=1 $, or $ j=n $) or adjacent (sharing a side) to an already filled position.
2. **Type 2**: Fill all empty positions in a $ 2 \times 2 $ square with the *same* correct block type, provided at least one position in the square is *free*.
- The square must lie entirely within the grid: $ 1 \leq x \leq n-1 $, $ 1 \leq y \leq n-1 $.
- No block may be placed in a position where the type does not match the chequered pattern.
- Total operations $ k \leq \frac{3n^2}{4} $.
**Objective**
Construct a sequence of $ k $ operations (each of Type 1 or Type 2) that fills the entire grid with the correct chequered pattern, starting from all empty positions, under the above constraints.