#P18602. Line Replacements

Line Replacements

Line Replacements

题目描述

Ordnungrad 的居民以生活中的井然有序为荣:街道干净,电车准点,市议会甚至宣布在城内犯罪不再可能,于是警察局也关闭了。这吸引了废品收集者 Byteasar。

城市的电车网络是一棵树:共有 nn 个交叉口和 n−1n-1 条双向轨道,任意两个交叉口之间恰有一条简单路径。其中 pp 个交叉口设有电车回转环线(下文简称“车环”)。所有树叶节点都有车环,其他节点也可能有。

Byteasar 选中了 kk 条照明不良的轨道,打算在接下来的每个夜晚恰好拆走其中一条。市议会为了掩盖此事,可以将其解释为维修,并在每天重新安排替代线路。然而居民要求:每条尚未拆走的轨道上,每小时每个方向的电车总班次数,都必须保持为原先测得的 cic_i。

更精确地说,第 jj 天(0≤j≤k0\le j\le k)必须能独立设计一套电车线路,满足:

  • 每条线路从某个车环出发,在另一个车环结束,沿树上的一条简单路径行驶。电车不能在不设车环的节点掉头,也不能走到某个节点后沿刚才的轨道立即返回。
  • 每条线路每小时运行一定的整数班次,两个方向的班次相同。
  • 线路不能经过前 jj 个夜晚已拆走的轨道。
  • 对任意尚未拆走的第 ii 条轨道,经过它的所有线路每小时在每个方向上合计恰好运行 cic_i 班。

每天的线路可以重新设计,不必与其他天的线路保持任何对应关系。

求一个合法的拆除顺序,或判断不存在。第 00 天也必须满足要求:测得的 cic_i 可能一开始就不能由任何合法线路网络实现,这种情况同样应回答无解。

输入格式

第一行一个整数 zz,表示测试用例数,1≤z≤150001\le z\le15000。

每个测试用例依次包含:

  1. 一行两个整数 n,pn,p,2≤p≤n≤5000002\le p\le n\le500000。
  2. 一行 pp 个严格递增的整数 p1,…,ppp_1,\ldots,p_p,表示有车环的交叉口编号,1≤pi≤n1\le p_i\le n。保证每个度数为 11 的交叉口都在其中。
  3. 接下来 n−1n-1 行,第 ii 行三个整数 ui,vi,ciu_i,v_i,c_i,表示编号为 ii 的轨道连接 ui,viu_i,v_i,每小时每个方向的要求班次为 cic_i。满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i、1≤ci≤1091\le c_i\le10^9,所有轨道构成一棵树。
  4. 一行一个整数 kk,1≤k≤n−11\le k\le n-1。
  5. 一行 kk 个严格递增的整数 k1,…,kkk_1,\ldots,k_k,表示要拆走的轨道编号,1≤ki≤n−11\le k_i\le n-1。

所有测试用例的 nn 之和不超过 20000002000000。

输出格式

对每个测试用例,若存在合法顺序,先输出一行 TAK,再输出一行 kk 个整数 r1,…,rkr_1,\ldots,r_k,表示第 ii 个夜晚拆走第 rir_i 条轨道。每条指定轨道必须恰好出现一次。

若有多种合法顺序,输出任意一种。

若不存在合法顺序,或初始班次数本身就无法由合法线路实现,输出一行 NIE。

样例输入 1

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

样例输出 1

TAK
2 3
NIE

样例说明

第一个测试用例可依次拆除轨道 2,32,3。以下各条线路的班次都指每小时、每个方向:

  • 拆除前:线路 1 ⁣→7 ⁣→21\!\to7\!\to2 运行 33 班,2 ⁣→7 ⁣→3 ⁣→5 ⁣→62\!\to7\!\to3\!\to5\!\to6 运行 11 班,3 ⁣→7 ⁣→43\!\to7\!\to4 运行 33 班。
  • 拆除轨道 22 后:线路 1 ⁣→7 ⁣→31\!\to7\!\to3、1 ⁣→7 ⁣→3 ⁣→5 ⁣→61\!\to7\!\to3\!\to5\!\to6、1 ⁣→7 ⁣→41\!\to7\!\to4 各运行 11 班,3 ⁣→7 ⁣→43\!\to7\!\to4 运行 22 班。
  • 再拆除轨道 33 后:线路 1 ⁣→7 ⁣→41\!\to7\!\to4 运行 33 班,3 ⁣→5 ⁣→63\!\to5\!\to6 运行 11 班。

倒过来输出 3,23,2 也是正确答案。

第二个测试用例还要拆除轨道 5,65,6。无论其中哪条先拆,另一条都会无法得到合法线路服务,所以无解。