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]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the number of towers.
- Let $ H_k = (h_{k,1}, h_{k,2}, \dots, h_{k,n_k}) $ be a sequence of distinct positive integers representing tower heights.
**Graph Construction**
Construct an undirected graph $ G_k = (V_k, E_k) $ where:
- $ V_k = \{1, 2, \dots, n_k\} $ (towers indexed left to right).
- For each tower $ i \in V_k $:
- Let $ \text{left}(i) $ be the largest index $ j < i $ such that $ h_{k,j} > h_{k,i} $, if it exists. Add edge $ (i, \text{left}(i)) $.
- Let $ \text{right}(i) $ be the smallest index $ j > i $ such that $ h_{k,j} > h_{k,i} $, if it exists. Add edge $ (i, \text{right}(i)) $.
- $ E_k $ is the set of all such edges.
**Constraints**
1. $ 1 \le T \le 128 $
2. $ 1 \le n_k \le 10^6 $ for each test case
3. $ \sum_{k=1}^T n_k \le 5 \times 10^6 $
4. All $ h_{k,i} $ are distinct.
**Objective**
Find the chromatic number $ \chi(G_k) $ of $ G_k $, and output a valid $ \chi(G_k) $-coloring of $ V_k $ such that no edge in $ E_k $ connects two vertices of the same color.