#P0071. 魔法少女的魔女审判

魔法少女的魔女审判

No testdata at current.

魔法少女的魔女审判

描述

现在即将举行【魔女审判】

在一座与世隔绝的孤岛上,存在 nn 名少女,她们的编号从 00 到 n−1n-1。一只会说话的猫头鹰宣告:岛上存在魔女,她们将会对人类社会造成威胁。现在少女们需要票选出魔女,将其亲手送上处刑台。

每一位少女 aia_i 仅有一次投票机会,她们可以作出的选择如下:

  • 指定另外一位其他的少女 bi(ai≠bi)b_i (a_i\neq b_i) 是魔女
  • 指定另外一位其他的少女 bi(ai≠bi)b_i (a_i\neq b_i) 不是魔女

为了确保审判的正义性,要求:

  • 要求 1:审判必须满足所有非魔女的投票结果。
  • 要求 2:被指定为魔女的数量严格小于非魔女的数量。
  • 要求 3:某位少女 aia_i 一旦被指定为魔女,进行连坐处理,即如果她指定 bib_i 不是魔女,bib_i 将被指定为魔女;反之,如果她指定 bib_i 是魔女,bib_i 将被指定为非魔女。

猫头鹰对其中一种情况进行推理,上述条件只要有一项不满足,则该情况无效;如果所有情况都无效,则审判无效,全员存活(详见说明)。

题目保证不会存在多个情况均有效,即要么情况满足且唯一,要么情况不满足全员存活。

其中,有一位叫樱羽艾玛的少女,她通过特殊手段获得了其他少女的投票结果,但代价是她只能指定其他的少女是魔女,现在轮到她最后投票。她明白仅通过票选出魔女太不讲理了,但她对此毫无办法,为了活下去,她需要保护自己。

规定樱羽艾玛的编号为0。可能存在不止一位魔女。

输入

第一行,一个正整数 nn,表示少女的数量。 接下来 n−1n-1 行,每行三个整数 aia_i、bib_i 和 qiq_i,表示:

  • 若 qi=0q_i=0 则 aia_i 指定 bib_i 不是魔女
  • 若 qi=1q_i=1 则 aia_i 指定 bib_i 是魔女。

数据保证 1≤n≤10001\leq n\leq 1000,1≤ai<n1\leq a_i\lt n,0≤bi<n0\leq b_i<n,qi∈{0,1}q_i\in\{0,1\}。

输出

输出一行,若樱羽艾玛能够通过投票达成全员存活,则输出 TE;若无法全员存活但她自己能活下去,则输出 NE;若她被送上处刑台,则输出 BE。

2
1 0 1
TE
3
1 0 1
2 0 1
BE

说明:

对于样例 1 少女 1 指定少女 0 (樱羽艾玛)是魔女。

假设樱羽艾玛指定少女 1 是魔女。所有情况如下:

  • 情况1:假设少女 1 是魔女,那么樱羽艾玛不是魔女(要求 3),此时魔女数量为 1,非魔女数量为 1(要求 2),情况无效。
  • 情况2:假设樱羽艾玛是魔女,同样的,那么少女 1 不是魔女,此时魔女数量为 1,非魔女数量为 1,情况无效。

所有情况均无效,因此审判无效,全员存活。

对于样例 2

少女 1 和 少女 2 均指定少女 0 (樱羽艾玛)是魔女。

假设樱羽艾玛指定少女 1 是魔女。所有情况如下:

  • 情况 1:假设少女 1 是魔女,那么樱羽艾玛不是魔女(要求 3),如果少女 2 不是魔女,由于条件 1 不满足,情况无效。
  • 情况 2:假设少女 1 和 2 都是魔女,那么樱羽艾玛不是魔女(要求 3),由于条件 2 不满足,情况无效。
  • 情况 3:假设樱羽艾玛是魔女,那么少女 1 不是魔女(要求 3),如果少女 2 不是魔女,所有条件均满足,因此情况有效。

樱羽艾玛指定少女 2 是魔女同理。

存在有效情况,因此审判有效,樱羽艾玛被送上处刑台。