まず，それぞれの「仲間」が情報を受け取ったときの最適な行動は以下のようなものです；

• スパイに情報を渡さないという条件下で，なるべくたくさんの仲間に情報を渡す

以下，この行動を前提とします．

仲間 \(i\) が仲間 \(j\) に情報を渡すとき，\(i\) から \(j\) に有向辺を張って，\(N\) 頂点の有向グラフ \(G\) を作ります．

\(G\) を強連結成分分解すると，次が成り立ちます．

• 他の成分から辺が入ってきていないような成分については，成分内の少なくとも一人に青木くんが直接情報を渡す必要がある．逆に，青木くんがそのように情報を渡せば，条件を達成できる．

よって，以下の手順で問題を解くことができます．

(1) グラフ \(G\) を作る．

(2) \(G\) を強連結成分分解する．

(3) 他の成分から辺が入ってきていないような成分を数える．

(1) は，各「仲間」に対して最も近い「スパイ」までの距離を求めることで可能です．

8sec という制約かつ計算も単純なので，\(\Theta(NM)\) 時間をかけての愚直な実装でもかなり余裕で間に合います．なお，KD Tree などを用いた高速化も可能です．

(2) は有名問題で，\(O(N^2)\) 時間でできます． なお，グラフ \(G\) を陽に持とうとすると，メモリ制限が厳しいので，実装によっては dfs の際に行き先の \(N\) 頂点をループしながら辺が存在するかを確認する空間計算量 \(O(N)\) の方法が役に立つと思います．

解答例：

• https://atcoder.jp/contests/arc010/submissions/42111921
• （KD Tree の利用）https://atcoder.jp/contests/arc010/submissions/42112279

実装によっては \(N=0\), \(M=0\) などがコーナーケースとなるので注意してください．