struct Dsu
{
T p[N];
void init()
{
for (int i = 1; i <= n; i ++ )
p[i] = i;
}
T find(T x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(T u, T v) { p[find(u)] = find(v); }
bool same(T u, T v) { return find(u) == find(v); }
} ;