原题链接:Problem - 1899F - Codeforces
题目大意:要求构建出一颗树,多次询问树的叶节点之间的距离有没有达到要求的距离,如果有直接输出-1 -1 -1,如果没有可以断开一条边和连上一条边,输出x y z,代表断开x-y,连接x-z。
思路:可以先构建一条链,然后移动第一个节点,去构成需要的距离。因为移动了第一个节点,那么第二个节点就变成了叶节点,就需要特判一下第n个节点和第二个节点的距离是否满足题意。
//冷静,冷静,冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll t;cin>>t;
while(t--)
{
ll n,q;cin>>n>>q;
for(int i=1;i<n;i++)
{
cout<<i<<' '<<i+1<<endl;//按照题意生成树
}
ll a=0,b=0,c=0;
while(q--)
{
ll dist;cin>>dist;
if(!a)//对于第一次移动特判一下
{
if(dist==n-1)
{
cout<<"-1 -1 -1"<<endl;
}
else
{
b=2;c=n-dist+1;
a=1;
cout<<a<<' '<<b<<' '<<c<<endl;
}
}
else
{
if(dist==n-2&&c!=2)//当第一个节点不和第二个节点相连接,那么就特判一下第二个节点和第n个节点
{
cout<<"-1 -1 -1"<<endl;
continue;
}
ll xa,xb,xc;
xa=1,xb=c,xc=n-dist+1;
if(xb==xc)
{
cout<<"-1 -1 -1"<<endl;//如果第一个节点没必要移动
}
else
{
cout<<xa<<' '<<xb<<' '<<xc<<endl;
a=xa,b=xb,c=xc;//移动第一个节点
}
}
}
}
return 0;
}