M. Cube Embedding
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Suppose we have a graph $$$G$$$ with vertex set $$$V$$$. A straight-line embedding of $$$G$$$ is a rendition of $$$G$$$ in 3D space such that the edges are straight line segments which do not intersect except possibly at their endpoints.

Formally, a function $$$f: V \to \mathbb{R}^3$$$ is called a straight-line embedding of $$$G$$$ if it satisfies the following conditions:

  • $$$f$$$ is injective; that is, $$$f(u) \neq f(v)$$$ when $$$u \neq v$$$.
  • For any pair of edges $$$(a, b)$$$ and $$$(c, d)$$$ in $$$G$$$, the line segment from $$$f(a)$$$ to $$$f(b)$$$ and the line segment from $$$f(c)$$$ to $$$f(d)$$$ do not intersect, except possibly by endpoints coinciding. In other words, no point of one segment may be in the interior of another segment.

Next, for $$$n \gt 0$$$, consider the cube of all points in $$$\mathbb{R}^3$$$ whose coordinates are in $$$[0, n+1]$$$. Denote this cube by $$$C_n$$$.

You are given a simple undirected graph $$$G$$$ (not necessarily connected) with vertices numbered $$$1$$$ through $$$n$$$ and the guarantee that for all vertices $$$v$$$, $$$v$$$ has degree at most $$$3$$$. Your task is to construct a straight-line embedding $$$f$$$ of $$$G$$$ such that for each $$$v$$$, the coordinates of $$$f(v)$$$ are all integers, and $$$f(v)$$$ lies on one of the 12 line segments comprising the edges of $$$C_n$$$.

It can be shown that, given the degree restriction on the vertices of $$$G$$$, such an embedding always exists.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n \le 5000$$$, $$$0 \le m \le \frac{3}{2}n$$$) — the number of vertices and edges respectively in $$$G$$$.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the vertices of an edge in $$$G$$$. It is guaranteed that all vertices have degree at most $$$3$$$ and that $$$G$$$ does not contain duplicate edges or self-loops.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

Output $$$n$$$ lines, each consisting of three integers. The integers on the $$$i$$$-th line represent the $$$x$$$, $$$y$$$, and $$$z$$$ coordinates respectively of $$$f(i)$$$, the image of vertex $$$i$$$ under your embedding. $$$(x, y, z)$$$ should lie on one of the edges of the cube.

If there are multiple solutions, print any.

Example
Input
2
5 5
1 2
2 3
3 4
2 4
4 5
5 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
1 6 6
6 0 3
2 0 6
2 0 0
0 6 3
6 6 6
0 1 0
1 0 0
0 0 1
0 2 6
Note

The first test case corresponds to the picture above.

Here is a visualization of the embedding for the second test case: