BZPRO

#5100. [POI2018]Plan metra

内存限制：128 MiB 时间限制：40 Sec
提交 提交记录 讨论

题目描述

有一棵n个点的无根树，每条边有一个正整数权值，表示长度，定义两点距离为在树上的最短路径的长度。
已知2到n-1每个点在树上与1和n的距离，请根据这些信息还原出这棵树。

输入格式

第一行包含一个正整数n(2<=n<=500000)，表示点数。
第二行包含n-2个正整数d(1,2),d(1,3),...,d(1,n-1)，分别表示每个点到1的距离。
第三行包含n-2个正整数d(n,2),d(n,3),...,d(n,n-1)，分别表示每个点到n的距离。
输入数据保证1<=d<=1000000。

输出格式

若无解，输出NIE。
否则第一行输出TAK，接下来n-1行每行三个正整数u,v,c(1<=u,v<=n,1<=c<=1000000)
表示存在一条长度为c的连接u和v两点的树边。
若有多组解，输出任意一组。

样例

样例输入


			
7

6 6 2 2 1

5 3 5 1 4

样例输出


			
TAK

1 5 2

5 7 1

5 2 4

7 3 3

1 4 2

1 6 1

数据范围与提示

BZPRO Powered by Remmina.
Github Repository