Start: Aug, 31, 2026 14:00:00
AI-prompt作业
End: Jan, 07, 2027 23:59:00
Time elapsed:
Time remaining:

三角剖分 3436

Time Limit:  1 s      Memory Limit:   256 MB
Submission:11     AC:0     Score:10

Description

圆上等距离分布着 n 个点,从某个点开始按顺时针方向编号从1 到 n。令 d 表示相邻两点之间的弧长。 

堡堡在圆上画了(2 * n − 3)条弦,每条弦都连接了n个点中的两个。保证不存在两条弦连接同一对点,且 不存在两条弦相交于圆的内部(不包括边界)。容易看出,这些弦构成了(n − 2)个三角形。这些三角 形称为圆的一个三角剖分。 

堡堡很喜欢这个三角剖分,所以他把这 (n − 2) 个三角形记在了一张纸上。第i个三角形用三个整数 ki,1 , ki,2 , ki,3 记录,其中 ki,j*d 是第 i 个三角形的第 j 个顶点到下一个顶点之间的最短弧长。对于j = 1 和 j = 2,它的下一个顶点是第 (j + 1) 个顶点。对于 j = 3,它的下一个顶点是第 1 个顶点。 

几天后,当堡堡想要再次欣赏三角剖分时,他失望地发现,所有的弦都被他的室友梦格擦掉了,所 以他只能根据纸上的信息还原三角剖分。您的任务是帮助堡堡确定 vi,j (对于所有 1 ≤ i ≤ n 以及 1 ≤ j ≤3),意思是第i个三角形的第j 个顶点是圆上的第vi,j 个点。堡堡也有可能记错了信息,这种情况下,您需要告诉堡堡这样的三角剖分并不存在。

Input

有多组测试数据。第一行输入一个整数T(1≤ T ≤104 )表示测试数据组数,对于每组测试数据: 第一行输入一个整数n(3 ≤ n ≤ 2×105 ),表示圆上点的数量。 对于接下来(n−2) 行,第i行输入三个整数 ki,1 , ki,2 , ki,3 (1≤ ki,j ≤ n / 2),其中 ki,j*d 是第 i 个三 角形的第 j 个顶点到下一个顶点之间的最短弧长。 保证所有数据n之和不超过2×105 。

Output

对于每组数据: 

• 如果存在这样的三角剖分,首先输出一行Yes。然后输出(n−2)行,其中第i行包含三个由单个 空格分隔的整数 vi,1 , vi,2 , vi,3 意思是第 i 个三角形的第 j 个顶点是圆上的第 vi,j 个点。如果有多 种合法答案,您可以输出任意一种。 

• 如果不存在这样的三角剖分,只要输出一行No。

Samples

input
3 3 1 1 1 4 1 1 1 1 2 1 6 3 1 2 1 2 1 1 3 2 1 2 1
output
Yes 3 2 1 No Yes 2 5 4 1 2 6 6 5 2 3 2 4