No.408

$1 \rightarrow x \rightarrow y$ ($y \neq 1$) となる $(x, y)$ の組の一覧を保持しておく.

道それぞれについて, $1 \rightarrow x_1 \rightarrow A_i$ と $1 \rightarrow x_2 \rightarrow B_i$ が組の一覧の中から見つかるかどうか, 見つかったとして $x_1 \neq x_2$ かどうかを調べる.

組の一覧を $y$ でソートして二分探索すれば高速に調べることができる.