33363번 - Graph Cuts 스페셜 저지다국어

문제

You are given an undirected graph without multiple edges or self-loops. You also have a set of its vertices $U$ that is initially empty. Your task is to answer queries of the following form.

1. "+ $v$". Add vertex $v$ to $U$. It is guaranteed that $v \not\in U$.
2. "- $v$". Remove vertex $v$ from $U$. It is guaranteed that $v \in U$.
3. "?". Find an edge such that exactly one of its endpoints is in $U$ and remove it from the graph, or determine that there are no such edges. If there are multiple edges that fulfill this property, you can choose any one of them.

입력

The first line contains two integers $n$ and $m$: the numbers of vertices and edges in the graph correspondingly (0ドル \le n, m \leq 10^5$). Each of the next $m$ lines contains two integers $u$ and $v$: the endpoints of a bidirectional edge (1ドル \leq u, v \leq n$). It is guaranteed that there are no multiple edges and no self-loops in the graph.

The next line contains a single integer $q,ドル the number of queries (0ドル \le q \leq 10^5$). The next $q$ lines contain queries in the format described above (1ドル \le v \le n$ in the queries).

출력

For each query of the third type, your program should either print a number of the found edge in the order it was presented in the input, or print 0ドル$ if such an edge does not exist.

제한

힌트