//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e5, block = 310;
bool del[N + 1];
struct controller
{
    int sum[(N + block - 1)/block + 1];
    int cur[N + 1], total;
    controller()
    {
        memset(sum, 0, sizeof(sum));
        memset(cur, 0, sizeof(cur));
        total = 0;
    }
    void toggle(int i)
    {
        if (del[i])
        {
            return ;
        }
        int b = (i + block - 1)/block;
        if (cur[i])
        {
            cur[i] = 0;
            --total;
            --sum[b];
        }
        else
        {
            cur[i] = 1;
            ++total;
            ++sum[b];
        }
    }
    int ans()
    {
        if (total == 0)
        {
            return 0;
        }
        for (int l = 1, b = 1; l <= N; l += block, ++ b)
        {
            if (sum[b] == 0)
            {
                continue;
            }
            for (int r = l; r <= min(N, l + block - 1); ++ r)
            {
                if (cur[r])
                {
                    return r;
                }
            }
            assert(false);
        }
    }
};
int x[N + 1], y[N + 1];
vector<int> adj[N + 1];
int n, m;
vector<int> big;
controller s, b[2][(N + block - 1)/block + 1];
bool in_v[N + 1];
int index[N + 1];
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
    {
        int u, v;
        cin >> u >> v;
        x[i] = u;
        y[i] = v;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
}
void solve()
{
    for (int u = 1, id = 0; u <= n; ++ u)
    {
        if (adj[u].size() > block)
        {
            index[u] = id;
            big.push_back(u);
            vector<int> t1, t2;
            for (int i : adj[u])
            {
                int v = x[i] ^ y[i] ^ u;
                b[1][id].toggle(i);
                if (adj[v].size() > block)
                {
                    t1.push_back(i);
                }
                else
                {
                    t2.push_back(i);
                }
            }
            adj[u].clear();
            adj[u].insert(end(adj[u]), begin(t1), end(t1));
            adj[u].insert(end(adj[u]), begin(t2), end(t2));
            // sort big child first
            ++id;
        }
    }
    int q;
    cin >> q;
    while(q--)
    {
        char c;
        cin >> c;
        if (c != '?')
        {
            int u;
            cin >> u;
            if (adj[u].size() <= block) // small
            {
                for (int i : adj[u])
                {
                    int v = x[i] ^ y[i] ^ u;
                    if (adj[v].size() <= block) // small - small
                    {
                        s.toggle(i);
                    }
                    else // big - small
                    {
                        int id_v = index[v];
                        b[0][id_v].toggle(i);
                        b[1][id_v].toggle(i);
                    }
                }
            }
            else //big
            {
                for (int i : adj[u])
                {
                    int v = x[i] ^ y[i] ^ u;
                    if (adj[v].size() <= block) // at most sqrt big child
                    {
                        break;
                    }
                    int id_v = index[v];
                    b[0][id_v].toggle(i);
                    b[1][id_v].toggle(i);
                }
            }
            in_v[u] ^= 1;
        }
        else
        {
            int res = s.ans();
            if (res != 0)
            {
                s.toggle(res);
                del[res] = true;
                cout << res << '\n';
                continue;
            }
            for (int u : big)
            {
                int id_u = index[u], cur_u = in_v[u];
                res = b[cur_u][id_u].ans();
                if (res != 0)
                {
                    int v = x[res] ^ y[res] ^ u;
                    assert(in_v[v] != in_v[u]);


                    b[cur_u][id_u].toggle(res);
                    if (adj[v].size() > block)
                    {
                        int id_v = index[v], cur_v = in_v[v];
                        b[cur_v][id_v].toggle(res);
                    }
                    del[res] = true;
                    break;
                }
            }
            cout << res << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

answer.code:67:16: error: ‘int index [100001]’ redeclared as different kind of entity
   67 | int index[N + 1];
      |                ^
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/13/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:121,
                 from answer.code:3:
/usr/include/strings.h:61:1: note: previous declaration ‘const char* index(const char*, int)’
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
answer.code: In function ‘void solve()’:
answer.code:87:18: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
   87 |             index[u] = id;
      |                  ^
answer.code:131:41: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
  131 |                         int id_v = index[v];
      |                                         ^
answer.code:146:37: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
  146 |                     int id_v = index[v];
      |                                     ^
answer.code:165:33: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
  165 |                 int id_u = index[u], cur_u = in_v[u];
      |                                 ^
answer.code:166:25: error: ‘cur_u’ was not declared in this scope
  166 |                 res = b[cur_u][id_u].ans();
      |                         ^~~~~
answer.code:176:41: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
  176 |                         int id_v = index[v], cur_v = in_v[v];
      |                                         ^
answer.code:177:27: error: ‘cur_v’ was not declared in this scope
  177 |                         b[cur_v][id_v].toggle(res);
      |                           ^~~~~
answer.code: In member function ‘int controller::ans()’:
answer.code:59:5: warning: control reaches end of non-void function [-Wreturn-type]
   59 |     }
      |     ^
answer.code: In function ‘int main()’:
answer.code:193:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  193 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~