友達の情報はグラフで管理する.

\(i\) さんと \(j\) の最短距離が \(d\) のとき, 1日経つとその距離は \(\lceil d/2 \rceil\) になる. 最短距離が \(1\) になるまでの日数を考えればいい. 当然ながら \(i\) さんと \(j\) さんが連結でない場合は友達にはなれない.

\(A_i\) さんが友達になれる最大の人数は BFS で探索し, その人数に達するまでの日数は \(A_i\) から一番遠い人までの距離から算出する. \(Q\) が小さいのでこれで間に合う.