#P18602. Line Replacements
Line Replacements
Line Replacements
题目描述
Ordnungrad 的居民以生活中的井然有序为荣:街道干净,电车准点,市议会甚至宣布在城内犯罪不再可能,于是警察局也关闭了。这吸引了废品收集者 Byteasar。
城市的电车网络是一棵树:共有 个交叉口和 条双向轨道,任意两个交叉口之间恰有一条简单路径。其中 个交叉口设有电车回转环线(下文简称“车环”)。所有树叶节点都有车环,其他节点也可能有。
Byteasar 选中了 条照明不良的轨道,打算在接下来的每个夜晚恰好拆走其中一条。市议会为了掩盖此事,可以将其解释为维修,并在每天重新安排替代线路。然而居民要求:每条尚未拆走的轨道上,每小时每个方向的电车总班次数,都必须保持为原先测得的 。
更精确地说,第 天()必须能独立设计一套电车线路,满足:
- 每条线路从某个车环出发,在另一个车环结束,沿树上的一条简单路径行驶。电车不能在不设车环的节点掉头,也不能走到某个节点后沿刚才的轨道立即返回。
- 每条线路每小时运行一定的整数班次,两个方向的班次相同。
- 线路不能经过前 个夜晚已拆走的轨道。
- 对任意尚未拆走的第 条轨道,经过它的所有线路每小时在每个方向上合计恰好运行 班。
每天的线路可以重新设计,不必与其他天的线路保持任何对应关系。
求一个合法的拆除顺序,或判断不存在。第 天也必须满足要求:测得的 可能一开始就不能由任何合法线路网络实现,这种情况同样应回答无解。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例依次包含:
- 一行两个整数 ,。
- 一行 个严格递增的整数 ,表示有车环的交叉口编号,。保证每个度数为 的交叉口都在其中。
- 接下来 行,第 行三个整数 ,表示编号为 的轨道连接 ,每小时每个方向的要求班次为 。满足 、、,所有轨道构成一棵树。
- 一行一个整数 ,。
- 一行 个严格递增的整数 ,表示要拆走的轨道编号,。
所有测试用例的 之和不超过 。
输出格式
对每个测试用例,若存在合法顺序,先输出一行 TAK,再输出一行 个整数 ,表示第 个夜晚拆走第 条轨道。每条指定轨道必须恰好出现一次。
若有多种合法顺序,输出任意一种。
若不存在合法顺序,或初始班次数本身就无法由合法线路实现,输出一行 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
样例说明
第一个测试用例可依次拆除轨道 。以下各条线路的班次都指每小时、每个方向:
- 拆除前:线路 运行 班, 运行 班, 运行 班。
- 拆除轨道 后:线路 、、 各运行 班, 运行 班。
- 再拆除轨道 后:线路 运行 班, 运行 班。
倒过来输出 也是正确答案。
第二个测试用例还要拆除轨道 。无论其中哪条先拆,另一条都会无法得到合法线路服务,所以无解。