#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" , size[ i] ) ; // displaying the size of the new set formed
} else {
size[ j] + = size[ i] ;
parent[ i] = parent[ j] ;
printf ( "%d" , 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" , size[ parent[ m[ f1] ] ] ) ;
if ( n > 0 )
printf ( "\n " ) ;
}
if ( t> 0 )
printf ( "\n " ) ;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXRoLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwptYXA8c3RyaW5nLCBpbnQ+IG07CmludCBzaXplWzEwMDAwMF0gPSB7MH07CmludCBwYXJlbnRbMTAwMDAwXTsKCmludCBmaW5kX3BhcmVudChpbnQgeCkgewogICAgaWYgKHBhcmVudFt4XSA9PSB4KSB7CiAgICAgICAgcmV0dXJuIHg7CiAgICB9IGVsc2UgewogICAgICAgIHBhcmVudFt4XSA9IHBhcmVudFtwYXJlbnRbeF1dOy8vIGFwcGx5aW5nIHBhdGggY29tcHJlc3Npb24KICAgICAgICByZXR1cm4gZmluZF9wYXJlbnQocGFyZW50W3hdKTsKICAgIH0KfQoKdm9pZCBkb191bmlvbihpbnQgeCwgaW50IHkpIHsKICAgIGludCBpLCBqOwogICAgZm9yIChpID0geDsgcGFyZW50W2ldICE9IGk7IGkgPSBwYXJlbnRbaV0pIHsKICAgICAgICBwYXJlbnRbaV0gPSBwYXJlbnRbcGFyZW50W2ldXTsvLyBhcHBseWluZyBwYXRoIGNvbXByZXNzaW9uCiAgICB9CiAgICBmb3IgKGogPSB5OyBwYXJlbnRbal0gIT0gajsgaiA9IHBhcmVudFtqXSkgewogICAgICAgIHBhcmVudFtqXSA9IHBhcmVudFtwYXJlbnRbal1dOy8vIGFwcGx5aW5nIHBhdGggY29tcHJlc3Npb24KICAgIH0KICAgIGlmIChzaXplW2ldID4gc2l6ZVtqXSkgey8vIGFkZGluZyB0aGUgc21hbGxlciBzZXQgdG8gdGhlIGxhcmdlciBzZXQKICAgICAgICBzaXplW2ldICs9IHNpemVbal07Ly8gYWRkaW5nIHRoZSBzbWFsbGVyIHNldCdzIHNpemUgdG8gdGhlIGxhcmdlciBzZXQncyBzaXplCiAgICAgICAgcGFyZW50W2pdID0gcGFyZW50W2ldOy8vIGFkanVzdGluZyB0aGUgcGFyZW50IHBvaW50ZXIgCiAgICAgICAgcHJpbnRmKCIlZCIsIHNpemVbaV0pOy8vIGRpc3BsYXlpbmcgdGhlIHNpemUgb2YgdGhlIG5ldyBzZXQgZm9ybWVkCiAgICB9IGVsc2UgewogICAgICAgIHNpemVbal0gKz0gc2l6ZVtpXTsKICAgICAgICBwYXJlbnRbaV0gPSBwYXJlbnRbal07CiAgICAgICAgcHJpbnRmKCIlZCIsIHNpemVbal0pOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIHN0cmluZyBmMSwgZjI7CiAgICBpbnQgdCwgbjsKICAgIHNjYW5mKCIlZCIsICZ0KTsgLy8gdGFraW5nIHRlc3QgY2FzZXMKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgaW5kZXggPSAxOwogICAgICAgIG0uY2xlYXIoKTsKICAgICAgICBtZW1zZXQoc2l6ZSwgMCwgc2l6ZW9mIChzaXplKSk7CiAgICAgICAgc2NhbmYoIiVkIiwgJm4pOyAvLyB0YWtpbmcgbm8gb2YgZnJpZW5kIHBhaXJzCiAgICAgICAgd2hpbGUgKG4tLSkgewogICAgICAgICAgICBjaW4gPj4gZjEgPj4gZjI7IC8vIHRha2luZyBmcmllbmQgcGFpcgogICAgICAgICAgICBpZiAoIW1bZjFdKSB7Ly8gaWYgIGZyaWVuZDEgZG9lc24ndCBleGlzdCwgcHV0IGYxIGluIHRoZSBtYXAgCiAgICAgICAgICAgICAgICBtW2YxXSA9IGluZGV4OwogICAgICAgICAgICAgICAgcGFyZW50W21bZjFdXSA9IGluZGV4Kys7Ly8gZjEgaXMgaXRzIG93biBwYXJlbnQgaW5pdGlhbGx5CiAgICAgICAgICAgICAgICBzaXplW21bZjFdXSsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmICghbVtmMl0pIHsvLyBpZiAgZnJpZW5kMSBkb2Vzbid0IGV4aXN0LCBwdXQgZjIgaW4gdGhlIG1hcAogICAgICAgICAgICAgICAgbVtmMl0gPSBpbmRleDsKICAgICAgICAgICAgICAgIHBhcmVudFttW2YyXV0gPSBpbmRleCsrOy8vIGYyIGlzIGl0cyBvd24gcGFyZW50IGluaXRpYWxseQogICAgICAgICAgICAgICAgc2l6ZVttW2YyXV0rKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoZmluZF9wYXJlbnQobVtmMV0pICE9IGZpbmRfcGFyZW50KG1bZjJdKSkvLyBpZiB0aGV5IGJlbG9uZyB0byBkaWZmZXJlbnQgc2V0cyBwcmludCB0aGUgc2l6ZSBvZiB0aGUgc2V0IGZvcm1lZCBhZnRlciB0aGVpdCB1bmlvbgogICAgICAgICAgICAgICAgZG9fdW5pb24obVtmMV0sIG1bZjJdKTsKICAgICAgICAgICAgZWxzZS8vIGVsc2UgcHJpbnQgdGhlIHNpemUgb2YgdGhlIGN1cnJlbnQgc2V0CiAgICAgICAgICAgICAgICBwcmludGYoIiVkIiwgc2l6ZVtwYXJlbnRbbVtmMV1dXSk7CiAgICAgICAgICAgIGlmIChuID4gMCkKICAgICAgICAgICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICB9CiAgICAgICAgaWYodD4wKQogICAgICAgICAgICBwcmludGYoIlxuIik7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=
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