# UVa 12096 - The SetStack Computer

---
# 題目大意
有一個元素是集合的stack，並有五種操作:
PUSH:裝一個空集合進去stack
DUP:複製stack最頂端的集合放進stack
UNION:拿stack最頂端兩個集合做聯集再放進stack
INTERSERT:拿stack最頂端兩個集合做交集再放進stack
ADD:把stack最頂端的集合拿出來插入stack新頂端的集合
每一次操作都要輸出stack最頂端集合的大小

---
# 題解
用兩個map，一個用來把集合編號，一個用來對應stack元素代表的集合。聯集和交集直接用STL做。

---

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int t ,n ,m ,u ,v;
map<set<int> ,int> mp1; //用整數代表set 
map<int ,set<int>> mp2; //用來找集合 
int sol(set<int> k)
{
	int res;
	if(!mp1.count(k)) res = mp1[k] = (int)mp1.size() ,mp2[res] = k;
	else res = mp1[k];
	return res;
}
string s;
int main() 
{
	ISCC;
	cin >> t; 
	while(t--)
	{
		cin >> n;
		stack<int> a;
		for(int i=0 ;i<n ;i++)
		{
			cin >> s;
			if(s=="PUSH") a.push(sol(set<int>()));
			if(s=="DUP") a.push(a.top());
			if(s=="ADD")
			{
				u = a.top(); a.pop();
				v = a.top(); a.pop();
				set<int> x=mp2[v];
				x.insert(u);
				a.push(sol(x));
			}
			if(s=="UNION")
			{
				u = a.top(); a.pop();
				v = a.top(); a.pop();
				set<int> x=mp2[u] ,y=mp2[v] ,z;
				set_union(x.begin() ,x.end() ,y.begin() ,y.end() ,inserter(z ,z.begin()));
				a.push(sol(z));
			}
			if(s=="INTERSECT")
			{
				u = a.top(); a.pop();
				v = a.top(); a.pop();
				set<int> x=mp2[u] ,y=mp2[v] ,z;
				set_intersection(x.begin() ,x.end() ,y.begin() ,y.end() ,inserter(z ,z.begin()));
				a.push(sol(z));
			}
			cout << (int)mp2[a.top()].size() << '\n';
			
		}
		cout << "***\n";
	}
	return 0;	
}