初始时有个首都1，有n个操作

+V表示有一个新的城市连接到了V号城市

-V表示V号城市断开了连接，同时V的子城市也会断开连接

每次输出在每次操作后到首都1距离最远的城市编号，多个距离相同输出编号最小的城市

输入数据保证正确，每次添加与删除的城市一定是与首都相连的


每次都只需要知道最远且编号最小的城市，所以直接使用优先队列存储

如果是+V就使用并查集（不能路径压缩）添加上然后加入优先队列，接着直接弹出首元素就是结果

如果是-V则把V指向0，接着弹出优先队列的第一个元素

如果他与1相连就是答案，否则将他到0这条路上的点都连上0删除他，继续弹出

注意这儿有个trick就是如果没有城市与1相连，答案就是1

然后为了避免这个trick,初始时刻就把1加到优先队列里就可以了。

//
//Created by just_sort 2016/12/30
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x, y) make_pair(x,y)
const int maxn = 100010;
const int maxm = 2e5;
const int maxs = 10;
const int INF = 1e9;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
struct node{
    int id, dis;
    node(){}
    node(int id, int dis) : id(id), dis(dis) {}
    bool operator<(const node &rhs) const{
        if(dis == rhs.dis)
            return id > rhs.id;
        return dis < rhs.dis;
    }
};
priority_queue <node> ans;
int fa[maxn], dis[maxn];
void init(int n){
    while(!ans.empty()) ans.pop();
    ans.push(node{1, 0});
    for(int i = 0; i <= n; i++) fa[i] = i, dis[i] = 0;
}
int Find(int x){
    if(x == fa[x]) return x;
    return Find(fa[x]);
}
void add(int f, int s){
    fa[s] = f;
    dis[s] = dis[f] + 1;
    ans.push(node(s, dis[s]));
}
void sub(int f){
    fa[f] = 0;
    while(!ans.empty()){
        node now = ans.top();
        if(Find(now.id) == 1) return ;
        int s = now.id;
        while(fa[s] != 0){
            fa[s] = 0;
            s = fa[s];
        }
        ans.pop();
    }
}
char cmd;
int main()
{
    int tt, x, n, newnode;
    scanf("%d", &tt);
    while(tt--){
        scanf("%d", &n);
        init(n + 1);
        newnode = 1;
        for(int i = 0; i < n; i++){
            getchar();
            scanf("%c%d", &cmd, &x);
            if(cmd == '+'){
                add(x, ++newnode);
            }
            else{
                sub(x);
            }
            node nn = ans.top();
            printf("%d\n", nn.id);
        }
    }
    return 0;
}