Description

每天，劫匪计划在某个地区抢劫恰好一家银行。由于卧底线人的工作，侦探们会在每天早上 $6$ 点之前得知劫匪当天要抢劫哪家银行。只要有一名侦探在银行，劫匪就会被吓退，因此侦探们需要合理安排自己的位置。抢劫会在银行开门后的白天（早上 $8$ 点后）进行，如果银行内没有侦探，抢劫就一定会成功。不幸的是，侦探的数量并不多，可能无法保护所有银行。为了保证效果，任何时刻每家银行最多只能有一名侦探。侦探只能在早上 $6$ 点到 $8$ 点之间离开当前银行并前往另一家银行。

只要有足够的天数，任何侦探都可以通过多次 $2$ 小时的转移，从任意一家银行到达另一家银行。但由于出行限制（主要是时间），侦探们只能在彼此相邻的银行之间移动。该地区的银行网络有如下特点：存在最少数量的相邻银行对，并且没有任何一家银行恰好与两家其他银行相邻。

现在，需要进行一次计算机模拟：判断劫匪在一年内（365 天）是否至少能成功抢劫一次。模拟程序将与预设的裁判程序进行对抗，类似于一场计算机游戏，且结果具有现实意义。在游戏中，攻击方代表劫匪，防守方负责调度侦探。

一开始，模拟程序会获得所有银行之间的相邻关系以及侦探的数量。然后，程序选择扮演攻击方或防守方，裁判自动扮演对方角色。接下来，防守方根据自己的选择将所有侦探安置在若干银行。

之后，游戏按回合进行。每回合，攻击方宣布要抢劫的一家银行，然后防守方可以让每名侦探沿着一条相邻银行的连线移动一次。防守方的目标是在回合结束时让被宣布的银行有侦探驻守。如果回合结束后该银行没有侦探，攻击方立即获胜。否则，防守方成功防守本回合，进入下一回合。如果防守方能连续防守一年（365 回合），则防守方获胜。游戏过程中，每名侦探的位置对双方都是公开的。

你需要编写一个模拟程序，智能地选择扮演的角色，以确保自己能够获胜。

交互模式

本题采用“交互模式”评测，即输入数据会根据你当前的输出动态生成。如果你没有相关经验也不用担心——你依然是从标准输入读取数据，向标准输出打印数据。只需注意以下几点：

每次输出响应后，必须刷新输出缓冲区。例如，在 C++ 中可以使用 fflush(stdout) 或 cout.flush()，在 Java 中用 System.out.flush()，在 Python 中用 stdout.flush()。同时，切勿尝试读取未准备好的输入数据，否则程序可能会无限等待。特别注意不要使用 scanf("%d ") 或 scanf("%d\n") 之类的格式，因为这些格式会试图读取后续的空白字符。应只使用 scanf("%d")，不要带尾随空白。

选择角色并输出后，以下交互最多重复 365 次：攻击方输出要攻击的银行编号 $0 \leq v \leq B-1$，防守方输出一个整数 $k$，随后输出 $k$ 对 $b_i, c_i$（$0 \leq b_i, c_i \leq B-1$），表示侦探从银行 $b_i$ 移动到银行 $c_i$。侦探只能沿着相邻银行之间的连线移动。攻击方在结束攻击时输出 $-1$。防守方可以通过结束程序放弃比赛。

在整个交互过程中，一方的输出始终作为另一方的输入。

Input Format

第一行输入两个整数 $B$ 和 $D$（$4 \leq B \leq 100, 0 \leq D \leq B$），分别表示银行数量和侦探数量。银行编号为 $0, 1, \ldots, B-1$。接下来的 $B-1$ 行，每行包含一对整数 $b_i, c_i$（$0 \leq b_i, c_i \leq B-1$），表示银行 $b_i$ 和 $c_i$ 之间有一条相邻连线。

Output Format

读入输入后，如果你选择攻击方，则输出一行 ATTACK。否则，输出一行 DEFEND，下一行输出 $D$ 个不同的银行编号（顺序任意），表示每名侦探的初始位置。后续交互过程按题目描述进行。

4 3
0 1
0 2
0 3


2

3

-1

DEFEND
0 1 2

0

2 1 0 0 3

4 1
0 1
0 2
0 3

0

1 0 1

ATTACK

1

2

Hint

为便于理解，样例数据中输入输出交错排列，展示了模拟程序与裁判的交互顺序。注意，实际数据中不会有空行，程序输出也不得有空行。

由 ChatGPT 4.1 翻译