SOCNETC - Social Network Community


Your friend came up with an idea of starting a social network-SOCNET. Since,he is not as good a programmer as you are he needs your help to build certain features.

You need to build an ADD friend feature. if 'x' sends a friend request to 'y',he may accept it or deny it.

SOCNET has a special feature called 'community'.When two people 'x' and 'y' becomes friends,the communities of two are merged together.(If 'x' has no friends,it's community consist of only himself,size-1)

Since,your friend is low on funds,the data center he uses has a restriction-the MAXIMUM size of any community cannot exceed 'm'.

You need to work on following three types of queries-

  • A x y - x sends a friend request to y
  • E x y - check whether x and y are present in same community(print 'Yes' or 'No')
  • S x - prints the size of the community 'x' belongs to.

NOTE- A friend requested is accepted only if the merger of the two communities results in a community not greater than 'm'.

Input

The first line of input consists of two positive integers - n and m(n is the number of registered users and m is the maximum size of any community).

Next line consist of a positive integer q(number of queries).

q lines follows(Each line consist of a query as described in the problem statement).

The queries follows 1-indexing.

Constraints

1<=n,m<=100000, 1<=q<=200000

Output

For each query of Type - 'E',output in a single line-'Yes' or 'No'. For each query of Type - 'S',output the size of the community to which 'x' belongs. For further clarification,read the example given.

Example

Input:
5 3
8
S 2
A 2 3
E 2 3
S 2
A 4 5
A 3 5
E 3 5
S 3


Output:
1
Yes
2
No
2


Explanation-Initially no one has any friend.So community of '2' consist of only '2' i.e size-1. Then '2' and '3' becomes friends .This forms a community of 2 people. '4' and '5' also becomes friends.This forms another community of 2 people. '5' is unable to accept friend request of '3' (because it would result in a community of 4 people(>3).

hide comments
jkks1234: 2018-01-17 13:45:21

https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/

akashranjan28: 2017-06-27 20:43:39

easiest one... it gave me 0.4 points
take care of "Yes"/"No" ,costed me 1 WA

Siddharth Singh: 2016-06-17 12:39:31

Silly Mistake Costed Me 3 WA's BC :|

ankit_amazon: 2016-03-21 21:21:20

Good one!

Arjav: 2016-01-24 01:38:23

Direct DSU :)

Prateek Agarwal: 2016-01-18 20:20:16

@levim-Either way is right.

levim: 2016-01-14 23:56:13

Do you print the results of all querys at the end of input or do you print after each query?

torque: 2015-12-27 19:49:00

AC in one go :)

abdou_93: 2015-12-20 17:36:32

Tutorial


Added by:Prateek Agarwal
Date:2015-12-20
Time limit:0.333s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY