首页 > 试题广场 >

三角网格

[编程题]三角网格
  • 热度指数:769 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
【注意:本题按通过的Case比例给分】

三角网格是计算机图形学中表示物体的常用形式,我们常用一个顶点索引和三角形索引表示具体网格。
在一个三角网格中,如果两个三角形共用同一条边则称这两个三角形是相连的,如果一个三角网格的任意两个三角形都直接或间接相连,则称这个三角网格是连通的。
如果一个三角网格可以展开成平面图,这称这个三角网格为平面三角网格,在平面三角网格中,单个三角形的顶点可以有顺时针或者逆时针两种排列,代表了三角形两种不同的朝向。
给定一个N个顶点,M个三角形组成的平面连通三角网格,需要你调整所有三角形索引的顶点顺序,使得所有三角形都和输入的第一个三角形具有相同的朝向,并且在每个三角形内部,序号最小的顶点放在首位。


输入描述:
第一行,两个整数N,M 表示有N个顶点和M个三角形 (3<=N<=400, 1<=M<800)
接下来M行,每行三个数字Ai, Bi, Ci(1<=Ai<=N, 1<=Bi<=N, 1<Ci<=N),表示第i个三角形的顶点序号


输出描述:
输出M行,每行三个数字,表示调整后的三角形顶点索引,输出的三角形顺序需要和输入保持一致。
示例1

输入

6 4
3 2 4
1 3 2
3 6 5
5 3 4

输出

2 4 3
1 2 3
3 5 6
3 4 5