Python の外部ライブラリには NetworkX というグラフ・ネットワークを扱えるものがあり、このコンテスト開催時点の AtCoder の環境では Python に分類される4種類全てで使えるようです。ただし、非常に遅いため使う場合は TLE を覚悟してください。

このライブラリの中に二部グラフであるかどうかを判定する関数is_bipartiteがあり、D問題はこの関数を使うことで簡潔に実装することができます。

実装例

import networkx as nx
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
g = nx.Graph()
for u,v in zip(a,b): g.add_edge(u,v)
print("Yes" if nx.is_bipartite(g) else "No")