#include <bits/stdc++.h>
using namespace std;
#define C const
#define U unsigned
#define SC static
#define CE constexpr
#define TL template
#define TN typename
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define mi (l + (r - l) / 2)
#define TTT TL<TN T = I>
#define TTI TL<TN It>
#define BE(v) v.begin(), v.end()
#define VD void
#define BL bool
#define CH char
#define I int
#define LL long long
#define II __int128
#define D double
#define STR string
using PII = pair<I, I>;
TTT using V = vector<T>;

#define FORX(v) for(auto& x : v)
#define FOR(i, b, e)  for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T

#define DR(T, ...) T __VA_ARGS__; R(__VA_ARGS__);
TTT VD R(T& x) { cin >> x; }
TTT T R() { DR(T, x); return x; }
TL<TN T, TN... A> VD R(T& x, A&... a) { R(x), R(a...); }
CE CH LF = '\n', SP = ' ';
TL<CH s = LF> VD W() { cout << s; }
TL<CH s = LF, TN T> VD W(C T& x) { cout << x << s; }
TL<CH s = LF, TN T, TN... A> VD W(C T& x, C A&... a) { W<SP>(x), W<s>(a...); }

TTT CE T inf() { return numeric_limits<T>::max() / 2; }
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }

TL<> struct std::hash<PII> { size_t OP()(C PII& p)C{ return (((size_t)p.ft) << 32) | p.sd; } };
VD test()
{
	DR(I, n, m);++n; I sqm = sqrt(m);
	V<I> dg(n), ish(n), vh;
	unordered_map<PII, I> eg;
	V<unordered_set<I>> s(n), d(n);
	unordered_set<PII> lde;

	FUNC(PII, make, I u, I v) { return u < v ? PII{ u, v } : PII{ v, u }; };
	FOR(i, 0, m)
	{
		DR(I, u, v);
		eg[make(u, v)] = i + 1;
		++dg[u], ++dg[v];
	}
	FOR(i, 1, n)if (dg[i] >= sqm)ish[i] = 1, vh.pb(i);
	FORX(eg)
	{
		I u = x.ft.ft, v = x.ft.sd;
		if (ish[u])s[u].insert(v);
		if (ish[v])s[v].insert(u);
		if (!ish[u] && !ish[v])s[u].insert(v), s[v].insert(u);
	}

	DR(I, q);
	while (q--)
	{
		DR(STR, op);
		if (op[0] != '?')
		{
			DR(I, p);
			if (!ish[p])
			{
				FORX(s[p])s[x].erase(p), d[x].insert(p), lde.insert(make(p, x));
				FORX(d[p])d[x].erase(p), s[x].insert(p), lde.erase(make(p, x));
			}
			swap(s[p], d[p]);
			FORX(vh)
			{
				if (x == p)continue;
				auto it = s[x].find(p);
				if (it != s[x].end())s[x].erase(it), d[x].insert(p);
				else
				{
					it = d[x].find(p);
					if (it != d[x].end())d[x].erase(it), s[x].insert(p);
				}
			}
		}
		else
		{
			I id = 0;
			if (lde.size())
			{
				auto it = lde.begin();
				id = eg[*it];
				I u = it->ft, v = it->sd;
				d[u].erase(v);
				d[v].erase(u);
				lde.erase(it);
			}
			else
			{
				FORX(vh)
				{
					if (d[x].empty())continue;
					I u = x, v = *d[x].begin();
					d[u].erase(v);
					if (ish[v])d[v].erase(u);
					id = eg[make(u, v)];
					break;
				}
			}
			W(id);
		}
	}
}

I main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	if (fopen("test.in", "r"))
	{
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	I t = 1;
	// R(t);
	while (t--)test();
	return 0;
}