记录编号	53329	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.124 s
提交时间	2013-02-25 21:03:03	内存使用	0.49 MiB

Program cog298;
    Var
        F,E:Array[1..50000]Of Longint;
        I,J,N,K,S,D,X,Y:Longint;
    Function G(A:Longint):Longint;
        Var
            H:Longint;
        Begin
            If F[A]=A Then Exit(A);
            H:=G(F[A]);
            E[A]:=(E[A]+E[F[A]]) Mod 3;
            F[A]:=H;
            Exit(H);
        End;
    Begin
        Assign(Input,'eat.in');
        Assign(Output,'eat.out');
        Reset(Input);
        Rewrite(Output);
        Readln(N,K);
        Fillchar(E,Sizeof(E),0);
        For I:=1 To N Do F[I]:=I;
        S:=0;
        Repeat
            Dec(K);
            Readln(D,X,Y);
            If (D=2) And (X=Y) Or (X>N) Or (Y>N)
                Then Begin
                        Inc(S);
                        Continue;
                     End;
            If (D=1) And (X=Y)
                Then Continue;
            I:=G(X);
            J:=G(Y);
            If I=J
                Then Begin
                         If (E[X]+E[Y] Shl 1) Mod 3<>D-1
                             Then Inc(S);
                         Continue;
                     End
                Else Begin
                         F[I]:=J;
                         E[I]:=(E[X] Shl 1+D-1+E[Y]) Mod 3;
                     End;
        Until K=0;
        Writeln(S);
        Close(Input);
        Close(Output);
    End.