#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 100'447;
VI g[N];
bool used[N];
int from[N];
int p[N];
map<PII, int> mp;
void dfs1(int v)
{
used[v] = true;
for (auto to : g[v])
{
if (!used[to])
{
from[to] = v;
dfs1(to);
}
}
}
int dfs2(int v, int par = -1)
{
p[v] = par;
for (auto to : g[v])
{
if (to == par)
continue;
if (to == 1)
return v;
int res = dfs2(to, v);
if (res != -1)
return res;
}
return -1;
}
void printKeys(const VI& v)
{
FOR (i, 0, SZ(v))
{
if (i)
cout << ' ';
cout << v[i];
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
FOR (i, 0, m)
{
int a, b;
cin >> a >> b;
mp[{a, b}] = i;
mp[{b, a}] = i;
g[a].PB(b);
g[b].PB(a);
}
used[1] = true;
dfs1(0);
int cnt = 0;
for (auto to : g[1])
{
if (used[to])
cnt++;
}
if (cnt >= 2)
{
int u = -1;
for (auto to : g[1])
{
if (used[to])
u = to;
}
int U = u;
VI path = {1, u};
while (u != 0)
{
u = from[u];
path.PB(u);
}
set<int> marichka;
FOR (i, 0, SZ(path) - 1)
{
marichka.insert(mp[{path[i], path[i + 1]}]);
}
VI zenyk;
FOR (i, 0, m)
if (!marichka.count(i))
zenyk.PB(i);
reverse(ALL(path));
VI mar(ALL(marichka));
printKeys(mar);
printKeys(zenyk);
FOR (i, 1, SZ(path))
{
cout << "MOVE " << path[i] << '\n';
if (i + 1 != SZ(path))
cout << "DROP " << mp[{path[i - 1], path[i]}] << '\n';
}
cout << "DONE\n";
path.clear();
int v = -1;
for (auto to : g[1])
{
if (used[to] && to != U)
v = to;
}
path = {1, v};
while (v != 0)
{
v = from[v];
path.PB(v);
}
FOR (i, 0, SZ(path) - 1)
{
int k = mp[{path[i], path[i + 1]}];
if (marichka.count(k))
cout << "GRAB\n";
cout << "MOVE " << path[i + 1] << '\n';
}
cout << "DONE\n";
}
else
{
if (cnt == 0)
{
cout << "No solution\n";
return 0;
}
int v = dfs2(1);
if (v == -1)
{
cout << "No solution\n";
return 0;
}
VI cycle = { 1, v };
while (v != 1)
{
v = p[v];
cycle.PB(v);
}
reverse(ALL(cycle));
int u = -1;
for (auto to : g[1])
{
if (used[to])
u = to;
}
VI path = {1, u};
while (u != 0)
{
u = from[u];
path.PB(u);
}
reverse(ALL(path));
set<int> marichka;
FOR (i, 0, SZ(path) - 1)
{
marichka.insert(mp[{path[i], path[i + 1]}]);
}
marichka.insert(mp[{1, v}]);
VI zenyk;
FOR (i, 0, m)
if (!marichka.count(i))
zenyk.PB(i);
VI mar(ALL(marichka));
printKeys(mar);
printKeys(zenyk);
FOR (i, 1, SZ(path))
{
cout << "MOVE " << path[i] << '\n';
if (i + 1 != SZ(path))
cout << "DROP " << mp[{path[i - 1], path[i]}] << '\n';
}
cout << "MOVE " << v << '\n';
cout << "DROP " << mp[{1, u}] << '\n';
cout << "MOVE " << 1 << '\n';
cout << "DONE\n";
FOR (i, 1, SZ(cycle) - 1)
{
cout << "MOVE " << cycle[i] << '\n';
}
cout << "GRAB\n";
RFOR (i, SZ(cycle) - 2, 0)
cout << "MOVE " << cycle[i] << '\n';
RFOR (i, SZ(path), 0)
{
cout << "GRAB\n";
cout << "MOVE " << path[i] << '\n';
}
cout << "DONE\n";
}
return 0;
}
0
1 2 3 4
MOVE 1
MOVE 1
DROP 0
MOVE 1
DONE
MOVE 2
MOVE 3
MOVE 4
GRAB
MOVE 3
MOVE 2
MOVE 1
GRAB
MOVE 1
GRAB
MOVE 0
DONE