#AC or RE ならば方針OK class Union_Find(): def __init__(self,N): """0,1,...,N-1を要素として初期化する. N:要素数 """ self.n=N self.parents=[-1]*N self.rank=[0]*N def find(self, x): """要素xの属している族を調べる. x:要素 """ V=[] while self.parents[x]>=0: V.append(x) x=self.parents[x] for v in V: self.parents[v]=x return x def union(self, x, y): """要素x,yを同一視する. x,y:要素 """ x=self.find(x) y=self.find(y) if x==y: return if self.rank[x]B[i]: A[i],B[i]=B[i],A[i] U=Union_Find(2*Q+2) s,t=0,2*Q+1 for i in range(Q): if A[i]==1: U.union(s,2*i+1) if B[i]==1: U.union(s,2*i+2) if A[i]==N: U.union(2*i+2,t) if B[i]==N: U.union(2*i+2,t) if B[i]-A[i]==1: U.union(2*i+1,2*i+2) if i>=1: j=i-1 if A[i]==A[j]: U.union(2*i+1,2*j+1) if A[i]==B[j]: U.union(2*i+1,2*j+2) if B[i]==A[j]: U.union(2*i+2,2*j+1) if B[i]==B[j]: U.union(2*i+2,2*j+2) if U.union(s,t): exit(print("NO")) print("YES") x=1/0