Alice 和 Bob 住在一座巨大的豪宅里，豪宅里有 $n$ 个房间（其中一个房间是户外，他们在那里玩“月球游戏”）以及 $m$ 扇门。每扇门连接两个房间，或者连接一个房间和户外，并且每扇门都有一把唯一的钥匙，只能打开这扇门。每扇门在你通过后会自动关闭并上锁，因此通过每扇门都需要对应的钥匙。这座建筑非常大，但 Alice 和 Bob 只使用一个房间——他们的卧室。其他房间的存在只是为了让房子看起来更大，并让邻居们嫉妒。

这种不同寻常的房屋建造方式现在给 Alice 和 Bob 带来了一些麻烦。Bob 即将开始为期两周的旅行。一周后，Alice 也要去国外待一个月，当她离开时，她需要正确的钥匙才能离开房子。然而，Bob 也需要钥匙才能回到房子里，因为 Alice 在他回来时不在家，无法为他开门。Alice 和 Bob 现在正试图弄清楚如何分配钥匙，以便 Alice 能从 0 号房间（他们的卧室）走到 1 号房间（户外），而 Bob 能在一周后从 1 号房间（户外）走到 0 号房间（卧室）。

幸运的是，Alice 记得她可以在离开的路上丢下一些钥匙，供 Bob 在回来的路上捡起。这样，他们都可以通过相同的门。当然，她不能在 1 号房间（户外）丢下任何钥匙，因为邻居可能会发现它们并闯入他们的房子。

你能帮助 Alice 和 Bob 分配钥匙并规划他们的行程吗？

题目描述

给定 Alice 和 Bob 的豪宅描述：$n$ 个房间（编号为 $0$ 到 $n-1$）之间有 $m$ 扇门，其中 $1$ 号房间是户外，$0$ 号房间是卧室。第 $i$ 扇门可以用编号为 $i$ 的钥匙打开（从 $0$ 开始编号）。

首先，你需要输出两行，分别包含 Alice 和 Bob 所持有的钥匙编号（用空格分隔）。他们不需要使用所有的钥匙，但严禁两人同时持有同一把钥匙的副本（或者其中一人持有同一把钥匙的多个副本）。

然后，你需要输出 Alice 和 Bob 将要遵循的指令。首先，通过输出以下两种类型的命令，打印 Alice 从 0 号房间移动到 1 号房间的过程：

• “MOVE x”：移动到房间 $x$（前提是 Alice 当前所在位置与 $x$ 之间有一扇门，且 Alice 持有该门的钥匙）。
• “DROP k1 k2 ...”：在 Alice 当前所在的房间丢下钥匙 $k_1, k_2, \dots$（以空格分隔的整数）。这意味着 Alice 不再携带这些钥匙。

当 Alice 完成她的移动后，在下一行输出 “DONE”。她最终应停在 1 号房间。在遵循打印的指令时，Alice 多次经过 0 号或 1 号房间是允许的。

其次，通过输出以下两种类型的命令，打印 Bob 从 1 号房间移动到 0 号房间的过程：

• “MOVE x”：移动到房间 $x$（前提是 Bob 当前所在位置与 $x$ 之间有一扇门，且 Bob 持有该门的钥匙）。
• “GRAB”：捡起 Bob 当前所在房间里的所有钥匙。Bob 总是会捡起 Alice 留在房间里的所有钥匙。如果 Alice 没有留下任何钥匙，他将不会捡起任何东西。

当 Bob 完成他的移动后，在下一行输出 “DONE”。他最终应停在 0 号房间。在遵循打印的指令时，Bob 多次经过 0 号或 1 号房间是允许的。

备注：丢下空的钥匙列表，或者在没有钥匙的房间里执行 GRAB，或者在 1 号房间（即户外）执行 GRAB，虽然没有实际用途，但均被视为可接受的操作。

输入格式

第一行包含整数 $n$ 和 $m$，分别表示房间数量（包含户外）和门的数量。接下来 $m$ 行描述这些门。第 $i$ 行（从 $0$ 开始计数）包含整数 $a_i, b_i$，表示房间 $a_i$ 和 $b_i$ 之间有一扇门，由钥匙 $i$ 打开。

数据范围

• $2 \le n, m \le 10^5$
• $0 \le a_i, b_i < n$
• 保证如果拥有所有钥匙，总是可以从任意房间到达其他任何房间。
• 每对房间之间最多由一扇门连接。
• 没有房间连接到自身。
• 你的程序最多可以输出 $4 \cdot 10^5$ 条指令。

输出格式

首先，输出两行，描述钥匙的分配情况。然后，按任务描述中说明的那样，逐行输出 Alice 和 Bob 的所有指令。如果没有解决方案，输出 “No solution”。如果存在多个有效的解决方案，输出其中任意一个即可。

样例

样例输入 1

5 5
0 1
1 2
2 3
3 4
4 1

样例输出 1

0 1 2
3 4
MOVE 1
MOVE 2
MOVE 3
DROP 0
MOVE 2
MOVE 1
DONE
MOVE 4
MOVE 3
GRAB
MOVE 4
MOVE 1
MOVE 0
DONE

样例输入 2

3 2
0 2
1 2

样例输出 2

No solution

说明

第一个样例代表了如下的平面图，其中蓝色数字对应每扇门所需的钥匙 ID：

Alice 持有钥匙 0、1 和 2，而 Bob 持有钥匙 3 和 4。Alice 从 0 走到 1，然后走到 2，最后走到 3。在那里，她丢下了钥匙 0。她原路返回到 1。Bob 从 1 出发，走到 4，然后走到 3，在那里他捡起了钥匙 0。他原路返回到 1，并用刚捡到的钥匙 0 打开了通往 0 的门。

在第二个样例中，Alice 和 Bob 无法同时到达他们的目的地。注意 Alice 不能在 1 号房间丢下钥匙。