#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>
using namespace std;
map< string, int > m;
int size[ 100000 ] = { 0 } ;
int parent[ 100000 ] ;
int find_parent( int x) {
if ( parent[ x] == x) {
return x;
} else {
parent[ x] = parent[ parent[ x] ] ; // applying path compression
return find_parent( parent[ x] ) ;
}
}
void do_union( int x, int y) {
int i, j;
for ( i = x; parent[ i] ! = i; i = parent[ i] ) {
parent[ i] = parent[ parent[ i] ] ; // applying path compression
}
for ( j = y; parent[ j] ! = j; j = parent[ j] ) {
parent[ j] = parent[ parent[ j] ] ; // applying path compression
}
if ( size[ i] > size[ j] ) { // adding the smaller set to the larger set
size[ i] + = size[ j] ; // adding the smaller set's size to the larger set's size
parent[ j] = parent[ i] ; // adjusting the parent pointer
printf ( "%d\n " , size[ i] ) ; // displaying the size of the new set formed
} else {
size[ j] + = size[ i] ;
parent[ i] = parent[ j] ;
printf ( "%d\n " , size[ j] ) ;
}
}
int main( ) {
string f1, f2;
int t, n;
scanf ( "%d" , & t) ; // taking test cases
while ( t-- ) {
int index = 1 ;
m.clear ( ) ;
memset ( size, 0 , sizeof ( size) ) ;
scanf ( "%d" , & n) ; // taking no of friend pairs
while ( n-- ) {
cin >> f1 >> f2; // taking friend pair
if ( ! m[ f1] ) { // if friend1 doesn't exist, put f1 in the map
m[ f1] = index;
parent[ m[ f1] ] = index++ ; // f1 is its own parent initially
size[ m[ f1] ] ++ ;
}
if ( ! m[ f2] ) { // if friend1 doesn't exist, put f2 in the map
m[ f2] = index;
parent[ m[ f2] ] = index++ ; // f2 is its own parent initially
size[ m[ f2] ] ++ ;
}
if ( find_parent( m[ f1] ) ! = find_parent( m[ f2] ) ) // if they belong to different sets print the size of the set formed after theit union
do_union( m[ f1] , m[ f2] ) ;
else // else print the size of the current set
printf ( "%d\n " , size[ parent[ m[ f1] ] ] ) ;
/*/if (n > 0)
printf("\n");*/
}
/*if(t>0)
printf("\n");*/
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXRoLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwptYXA8c3RyaW5nLCBpbnQ+IG07CmludCBzaXplWzEwMDAwMF0gPSB7MH07CmludCBwYXJlbnRbMTAwMDAwXTsKCmludCBmaW5kX3BhcmVudChpbnQgeCkgewogICAgaWYgKHBhcmVudFt4XSA9PSB4KSB7CiAgICAgICAgcmV0dXJuIHg7CiAgICB9IGVsc2UgewogICAgICAgIHBhcmVudFt4XSA9IHBhcmVudFtwYXJlbnRbeF1dOy8vIGFwcGx5aW5nIHBhdGggY29tcHJlc3Npb24KICAgICAgICByZXR1cm4gZmluZF9wYXJlbnQocGFyZW50W3hdKTsKICAgIH0KfQoKdm9pZCBkb191bmlvbihpbnQgeCwgaW50IHkpIHsKICAgIGludCBpLCBqOwogICAgZm9yIChpID0geDsgcGFyZW50W2ldICE9IGk7IGkgPSBwYXJlbnRbaV0pIHsKICAgICAgICBwYXJlbnRbaV0gPSBwYXJlbnRbcGFyZW50W2ldXTsvLyBhcHBseWluZyBwYXRoIGNvbXByZXNzaW9uCiAgICB9CiAgICBmb3IgKGogPSB5OyBwYXJlbnRbal0gIT0gajsgaiA9IHBhcmVudFtqXSkgewogICAgICAgIHBhcmVudFtqXSA9IHBhcmVudFtwYXJlbnRbal1dOy8vIGFwcGx5aW5nIHBhdGggY29tcHJlc3Npb24KICAgIH0KICAgIGlmIChzaXplW2ldID4gc2l6ZVtqXSkgey8vIGFkZGluZyB0aGUgc21hbGxlciBzZXQgdG8gdGhlIGxhcmdlciBzZXQKICAgICAgICBzaXplW2ldICs9IHNpemVbal07Ly8gYWRkaW5nIHRoZSBzbWFsbGVyIHNldCdzIHNpemUgdG8gdGhlIGxhcmdlciBzZXQncyBzaXplCiAgICAgICAgcGFyZW50W2pdID0gcGFyZW50W2ldOy8vIGFkanVzdGluZyB0aGUgcGFyZW50IHBvaW50ZXIgCiAgICAgICAgcHJpbnRmKCIlZFxuIiwgc2l6ZVtpXSk7Ly8gZGlzcGxheWluZyB0aGUgc2l6ZSBvZiB0aGUgbmV3IHNldCBmb3JtZWQKICAgIH0gZWxzZSB7CiAgICAgICAgc2l6ZVtqXSArPSBzaXplW2ldOwogICAgICAgIHBhcmVudFtpXSA9IHBhcmVudFtqXTsKICAgICAgICBwcmludGYoIiVkXG4iLCBzaXplW2pdKTsKICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBzdHJpbmcgZjEsIGYyOwogICAgaW50IHQsIG47CiAgICBzY2FuZigiJWQiLCAmdCk7IC8vIHRha2luZyB0ZXN0IGNhc2VzCiAgICB3aGlsZSAodC0tKSB7CiAgICAgICAgaW50IGluZGV4ID0gMTsKICAgICAgICBtLmNsZWFyKCk7CiAgICAgICAgbWVtc2V0KHNpemUsIDAsIHNpemVvZiAoc2l6ZSkpOwogICAgICAgIHNjYW5mKCIlZCIsICZuKTsgLy8gdGFraW5nIG5vIG9mIGZyaWVuZCBwYWlycwogICAgICAgIHdoaWxlIChuLS0pIHsKICAgICAgICAgICAgY2luID4+IGYxID4+IGYyOyAvLyB0YWtpbmcgZnJpZW5kIHBhaXIKICAgICAgICAgICAgaWYgKCFtW2YxXSkgey8vIGlmICBmcmllbmQxIGRvZXNuJ3QgZXhpc3QsIHB1dCBmMSBpbiB0aGUgbWFwIAogICAgICAgICAgICAgICAgbVtmMV0gPSBpbmRleDsKICAgICAgICAgICAgICAgIHBhcmVudFttW2YxXV0gPSBpbmRleCsrOy8vIGYxIGlzIGl0cyBvd24gcGFyZW50IGluaXRpYWxseQogICAgICAgICAgICAgICAgc2l6ZVttW2YxXV0rKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoIW1bZjJdKSB7Ly8gaWYgIGZyaWVuZDEgZG9lc24ndCBleGlzdCwgcHV0IGYyIGluIHRoZSBtYXAKICAgICAgICAgICAgICAgIG1bZjJdID0gaW5kZXg7CiAgICAgICAgICAgICAgICBwYXJlbnRbbVtmMl1dID0gaW5kZXgrKzsvLyBmMiBpcyBpdHMgb3duIHBhcmVudCBpbml0aWFsbHkKICAgICAgICAgICAgICAgIHNpemVbbVtmMl1dKys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKGZpbmRfcGFyZW50KG1bZjFdKSAhPSBmaW5kX3BhcmVudChtW2YyXSkpLy8gaWYgdGhleSBiZWxvbmcgdG8gZGlmZmVyZW50IHNldHMgcHJpbnQgdGhlIHNpemUgb2YgdGhlIHNldCBmb3JtZWQgYWZ0ZXIgdGhlaXQgdW5pb24KICAgICAgICAgICAgICAgIGRvX3VuaW9uKG1bZjFdLCBtW2YyXSk7CiAgICAgICAgICAgIGVsc2UvLyBlbHNlIHByaW50IHRoZSBzaXplIG9mIHRoZSBjdXJyZW50IHNldAogICAgICAgICAgICAgICAgcHJpbnRmKCIlZFxuIiwgc2l6ZVtwYXJlbnRbbVtmMV1dXSk7CiAgICAgICAgICAgIC8qL2lmIChuID4gMCkKICAgICAgICAgICAgICAgIHByaW50ZigiXG4iKTsqLwogICAgICAgIH0KICAgICAgICAvKmlmKHQ+MCkKICAgICAgICAgICAgcHJpbnRmKCJcbiIpOyovCiAgICB9CiAgICByZXR1cm4gMDsKfQo=
stdin
MTAKMzAKdyBuCnIgbApiIGIKcSBtCmggYgpkIGMKciBhCm8gegprIHcKeSBrCmkgaApkIGQKcyBxCmQgYwpyIHgKbSBqCncgbwpyIGYKcyB4CnkgagpsIGIKYiBkCmYgZQphIHMKYyByCnkgYgplIG4KZCBjCmcgeQp4IGcKMzAKcCB4CmwgawpyIG8KbCBlCm4gbApwIG0KcCBhCmYgcQprIHcKbyBoCmsgcApjIG0KcSBvCm4gaApuIHcKdSBrCncgZQpzIGgKbSBxCmIgZwp1IGIKYyBxCmogbAppIGoKcyB2Cm0gdwprIGQKdCBxCnggYgp4IGkKMzAKdiBtCnIgdApiIHIKaiBsCnQgcApzIG4KZiBuCnogdwpmIHEKbSBqCmYgYQpkIGEKciByCnMgdwpmIG8KYiBzCm4gYwp2IHUKaCBxCmYgZgpzIGIKcSBhCncgeApxIHAKYSBjCmUgYwpjIGgKeiBoCmYgdgprIHIKMzAKbCBtCm8gbgpqIHoKcCBrCnAgcQpyIHgKeCBqCmkgawp6IHQKeCB5CmMgYQpoIGIKayBoCmMgaQpjIHEKZSBvCmQgbgpvIHQKZiBtCmQgZwpkIHcKZiB3CmcgYwp4IHAKcSBpCmsgdgp5IHUKZCB0CmMgbApkIGcKMzAKdyBlCnQgaApjIGEKbyBpCm8gaApkIHIKcSB0CnYgawpjIHcKZyBzCnAgcwpvIHEKbSBxCmIgcwphIG8KdSBnCm4gdwp5IG4KeCBxCnogbgpnIGwKZyBkCnAgdwp0IGIKdyByCmwgYgpzIG4KZCBhCnUgZQp1IGcKMzAKbSB1CnEgbwpkIGMKdSByCmUgYgpvIHQKeSBrCmggeAphIG8KaCBjCmQgdwptIHYKeCB4CmQgcgp5IHIKbCB4Cm4gbQpxIGQKdSB0CncgawpnIGEKbCBtCmogZQp1IHUKdyBrCmkgYwp4IGIKYiB1Cm0gdQpuIGUKMzAKZSBtCmEgeQpkIHQKbSByCmQgeQphIGkKeCBqCm8gbApoIGcKcSBpCm0gZgpoIHoKdiBsCmggaQpvIGoKdiB1CnUgcwpvIHkKcCB5CnkgYQpsIHUKZSB5Cm0gaQpvIHUKZSB0CnogaAppIHIKYyBpCnMgZgpwIGsKMzAKZyBnCmIgawppIGIKeiBwCnIgegp1IHoKeCBjCm0gYQp1IGwKZiBkCmsgeQpyIGcKbyB1CnogdwppIGcKbyBvCmIgbwpwIHAKZSBsCmwgcQpwIHcKYSBoCmogcAphIG4KcSBkCmQgaApuIGMKdyB2CnQgZApqIHgKMzAKbSBiCnAgeQpwIHAKYSBoCnggdQpzIG4KdSBwCmcgcwpoIGQKaSBpCnEgeApiIG0KaiBmCmogeAp2IGMKZCB1CnMgagp5IHUKYiBpCmUgeQptIGIKcyB3CnEgaQpvIHkKZyB5CnggeQptIHkKZSB6Cnkgdgp6IHAKMzAKaiB2CmcgZQpiIGUKbyBlCmYgYwpmIHUKcyB0CmQgeAp4IGkKaSB0CnMgZwplIGkKaCBlCmMgawp6IGgKZiBkCmkgbApyIGwKcSBqCm4gZgp6IHgKcSB0CnMgcgpiIHYKcCBzCnkgawpzIGgKbiBlCnAgYgprIHA=
10
30
w n
r l
b b
q m
h b
d c
r a
o z
k w
y k
i h
d d
s q
d c
r x
m j
w o
r f
s x
y j
l b
b d
f e
a s
c r
y b
e n
d c
g y
x g
30
p x
l k
r o
l e
n l
p m
p a
f q
k w
o h
k p
c m
q o
n h
n w
u k
w e
s h
m q
b g
u b
c q
j l
i j
s v
m w
k d
t q
x b
x i
30
v m
r t
b r
j l
t p
s n
f n
z w
f q
m j
f a
d a
r r
s w
f o
b s
n c
v u
h q
f f
s b
q a
w x
q p
a c
e c
c h
z h
f v
k r
30
l m
o n
j z
p k
p q
r x
x j
i k
z t
x y
c a
h b
k h
c i
c q
e o
d n
o t
f m
d g
d w
f w
g c
x p
q i
k v
y u
d t
c l
d g
30
w e
t h
c a
o i
o h
d r
q t
v k
c w
g s
p s
o q
m q
b s
a o
u g
n w
y n
x q
z n
g l
g d
p w
t b
w r
l b
s n
d a
u e
u g
30
m u
q o
d c
u r
e b
o t
y k
h x
a o
h c
d w
m v
x x
d r
y r
l x
n m
q d
u t
w k
g a
l m
j e
u u
w k
i c
x b
b u
m u
n e
30
e m
a y
d t
m r
d y
a i
x j
o l
h g
q i
m f
h z
v l
h i
o j
v u
u s
o y
p y
y a
l u
e y
m i
o u
e t
z h
i r
c i
s f
p k
30
g g
b k
i b
z p
r z
u z
x c
m a
u l
f d
k y
r g
o u
z w
i g
o o
b o
p p
e l
l q
p w
a h
j p
a n
q d
d h
n c
w v
t d
j x
30
m b
p y
p p
a h
x u
s n
u p
g s
h d
i i
q x
b m
j f
j x
v c
d u
s j
y u
b i
e y
m b
s w
q i
o y
g y
x y
m y
e z
y v
z p
30
j v
g e
b e
o e
f c
f u
s t
d x
x i
i t
s g
e i
h e
c k
z h
f d
i l
r l
q j
n f
z x
q t
s r
b v
p s
y k
s h
n e
p b
k p