Online Communities - Even Groups

    

    In a social network, online communities refer to the group of people with an interest towards the same topic. People connect with each other in a social network. A connection between Person I and Person J is represented as C I J. When two persons belonging to different communities connect, the net effect is merger of both communities which I and J belonged to.

    We are only interested in finding out the communities with the member count being an even number. Your task is to find out those communities.

Input Format:

Input will consist of three parts, viz.

1. The total number of people on the social network (N)
2.Queries 

• C I J, connect I and J
• Q 0 0, print the number of communities with even member-count

-1 will represent end of input.

Output Format

    For each query Q, output the number of communities with even member-count

Constraints:

1<=N<=10^6

1<=I, J<=N

Sample Input and Output

    Input
    5
    Q 0 0
    C 1 2
    Q 0 0
    C 2 3
    Q 0 0
    C 4 5
    Q 0 0
    -1

    Output

    0
    1
    0
    1

Explanation:

For first query there are no members in any of the groups hence answer is 0.
After C 1 2, there is a group (let's take it as G1) with 1 and 2 as members hence total count at this moment is 1.
After C 2 3 total members in G1 will become {1, 2, 3} hence there are no groups with even count.
After C 4 5 there formed a new group G2 with {4, 5} as members, hence the total groups with even count is 1.

Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.

Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc