记录编号	70343	评测结果	AAWAAAAAAW
题目名称	[郑州101中学] Assassin	最终得分	80
用户昵称	Ezoi_XY	是否通过	未通过
代码语言	Pascal	运行时间	0.578 s
提交时间	2013-09-26 17:25:01	内存使用	17.33 MiB

Program cog1178;
    Var
        Q,H,Ne,E:Array[1..1000010]Of Longint;
        D,X:Array[1..1000010]Of Shortint;
        T,N,M,I,J,K,S:Longint;
    Procedure Pr(A:Longint);
        Begin
            If A<>-1
                Then Writeln(A)
                Else Writeln('NO');
            Close(Input);
            Close(Output);
            Halt;
        End;
    Procedure Ins(A,B:Longint);
        Begin
            Inc(T);
            Ne[T]:=H[A];
            H[A]:=T;
            E[T]:=B;
        End;
    Procedure Bfs;
        Var
            I,L,R:Longint;
        Begin
            L:=0;
            R:=1;
            Q[1]:=1;
            While L<>R Do
                Begin
                    Inc(L);
                    I:=H[Q[L]];
                    While I<>0 Do
                        Begin
                            If X[E[I]]<>-1 Then
                                Begin
                                    If X[E[I]]=X[Q[L]] Then Pr(-1);
                                    I:=Ne[I];
                                    Continue;
                                End;
                            X[E[I]]:=X[Q[L]] Xor 1;
                            Inc(S,X[E[I]]*D[E[I]]);
                            Inc(R);
                            Q[R]:=E[I];
                            I:=Ne[I];
                        End;
                End;
        End;
    Begin
        Assign(Input,'assassin.in');
        Assign(Output,'assassin.out');
        Reset(Input);
        Rewrite(Output);
        T:=0;
        Readln(N,M);
        Filldword(H,N+1,0);
        For I:=1 To N Do Read(D[I]);
        For I:=1 To M Do
            Begin
                Readln(J,K);
                Ins(J,K);
                Ins(K,J);
            End;
        Fillchar(X,N+1,$FF);
        S:=D[1];
        X[1]:=1;
        Bfs;
        I:=S;
        Fillchar(X,N+1,$FF);
        S:=0;
        X[1]:=0;
        Bfs;
        If I<S
            Then Pr(I)
            Else Pr(S);
    End.