Zurikela's Grapgh

 Zurikela is creating a graph with a special graph maker. At the begining, it is empty and has no nodes or edges. He can perform  types of operations:

1.  : Create a set of  new nodes and name it -.
2.   : Create edges between nodes of - and -.
3.  : Create a set composed of nodes from - and its directly and indirectly connected nodes, called -. Note that each node can only exist in one set, so other sets become empty.

The first 's name will be -. In first and third operation  is referring to the index of new set:

K = [index of last created set] + 1

Create the graph by completing the  operations specified during input. Then calculate the maximum number of independent nodes (i.e.:how many nodes in the final graph which don't have direct edge between them).

Input Format

The first line contains .
The  subsequent lines each contain an operation to be performed.

Constraints
.
For the first operation, .
For the second operation,  and all s are distinct.
For the second and third operation, it's guaranteed that - and - exist.

Output Format

Print maximum number of independent nodes in the final graph (i.e.: nodes which have no direct connection to one another).

Sample Input

8
A 1
A 2
B 1 2
C 1
A 2
A 3
B 3 4
B 4 5

Sample Output

5

Explanation

There are  operations.

After first operation:

After second operation:

After third operation:

After fourth operation:

After fifth and sixth operation  and :

After seventh operation: 

After eigth operation:

There are  independent nodes in - and  independent nodes in -, so we print their sum () as our answer.

#include <stdio.h>

#include <stdlib.h>

typedef struct node{

  int x;

  int w;

  struct node *next;

} lnode;

void insert_edge(int x,int y,int w);

void dfs(int x,int y);

int max(int x,int y);

char str[2];

int a[100000],dp1[2][100000],track[100000]={0};

lnode *table[100000]={0};

int main(){

  int Q,x,y,c=0;

  scanf("%d",&Q);

  while(Q--){

    scanf("%s",str);

    switch(str[0]){

      case 'A':

        scanf("%d",&x);

        a[c++]=x;

        break;

      case 'B':

        scanf("%d%d",&x,&y);

        insert_edge(x-1,y-1,1);

        break;

      default:

        scanf("%d",&x);

        dfs(x-1,-1);

        a[c++]=max(dp1[0][x-1],dp1[1][x-1]);

    }

  }

  for(x=y=0;x<c;x++)

    if(!track[x]){

      dfs(x,-1);

      y+=max(dp1[0][x],dp1[1][x]);

    }

  printf("%d",y);

  return 0;

}

void insert_edge(int x,int y,int w){

  lnode *t=malloc(sizeof(lnode));

  t->x=y;

  t->w=w;

  t->next=table[x];

  table[x]=t;

  t=malloc(sizeof(lnode));

  t->x=x;

  t->w=w;

  t->next=table[y];

  table[y]=t;

  return;

}

void dfs(int x,int y){

  lnode *p;

  track[x]=1;

  for(p=table[x];p;p=p->next)

    if(p->x!=y)

      dfs(p->x,x);

  dp1[1][x]=0;

  dp1[0][x]=a[x];

  for(p=table[x];p;p=p->next)

    if(p->x!=y){

      dp1[0][x]+=dp1[1][p->x];

      if(dp1[0][p->x]>dp1[1][p->x])

        dp1[1][x]+=dp1[0][p->x];

      else

        dp1[1][x]+=dp1[1][p->x];

    }

  return;

}

int max(int x,int y){

  return (x>y)?x:y;

}