結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー 👑 KazunKazun
提出日時 2022-02-11 02:18:37
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 1,403 ms / 4,000 ms
コード長 25,039 bytes
コンパイル時間 922 ms
コンパイル使用メモリ 87,344 KB
実行使用メモリ 259,096 KB
最終ジャッジ日時 2023-07-30 11:11:02
合計ジャッジ時間 33,005 ms
ジャッジサーバーID
(参考情報)
judge13 / judge5
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
72,360 KB
testcase_01 AC 93 ms
72,444 KB
testcase_02 AC 94 ms
72,384 KB
testcase_03 AC 97 ms
72,168 KB
testcase_04 AC 97 ms
72,168 KB
testcase_05 AC 95 ms
72,384 KB
testcase_06 AC 97 ms
72,356 KB
testcase_07 AC 96 ms
72,452 KB
testcase_08 AC 202 ms
81,720 KB
testcase_09 AC 212 ms
88,352 KB
testcase_10 AC 323 ms
87,984 KB
testcase_11 AC 323 ms
88,336 KB
testcase_12 AC 239 ms
83,188 KB
testcase_13 AC 820 ms
171,492 KB
testcase_14 AC 901 ms
177,608 KB
testcase_15 AC 1,005 ms
232,936 KB
testcase_16 AC 671 ms
242,268 KB
testcase_17 AC 946 ms
180,180 KB
testcase_18 AC 951 ms
238,404 KB
testcase_19 AC 1,214 ms
248,480 KB
testcase_20 AC 919 ms
222,644 KB
testcase_21 AC 997 ms
204,308 KB
testcase_22 AC 1,142 ms
199,868 KB
testcase_23 AC 1,350 ms
254,636 KB
testcase_24 AC 1,375 ms
253,412 KB
testcase_25 AC 1,374 ms
256,716 KB
testcase_26 AC 1,385 ms
253,380 KB
testcase_27 AC 1,403 ms
251,744 KB
testcase_28 AC 1,402 ms
254,988 KB
testcase_29 AC 1,327 ms
253,348 KB
testcase_30 AC 1,336 ms
253,216 KB
testcase_31 AC 1,316 ms
256,760 KB
testcase_32 AC 1,380 ms
251,740 KB
testcase_33 AC 98 ms
71,976 KB
testcase_34 AC 507 ms
254,476 KB
testcase_35 AC 589 ms
259,096 KB
testcase_36 AC 723 ms
247,160 KB
testcase_37 AC 100 ms
72,324 KB
testcase_38 AC 148 ms
81,268 KB
testcase_39 AC 578 ms
238,460 KB
testcase_40 AC 551 ms
215,584 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

class Union_Find():
    __slots__=["n","parents","rank","edges","__group_number"]
    def __init__(self,N):
        """ 0,1,...,N-1 を要素として初期化する.

        N: 要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N
        self.edges=[0]*N
        self.__group_number=N

    def find(self, x):
        """ 要素 x の属している族を調べる.

        x: 要素
        """

        a=x
        while self.parents[a]>=0:
            a=self.parents[a]

        while self.parents[x]>=0:
            self.parents[x]=a
            x=self.parents[x]

        return a

    def union(self, x, y):
        """ 要素 x,y を同一視する.

        [input]
        x,y: 要素

        [output]
        元々が非連結 → True
        元々が連結 → False
        """
        x=self.find(x)
        y=self.find(y)

        if x==y:
            self.edges[x]+=1
            return False

        if self.rank[x]<self.rank[y]:
            x,y=y,x

        self.__group_number-=1

        self.edges[x]+=self.edges[y]+1
        self.edges[y]=0

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1
        return True

    def size(self, x):
        """ 要素 x の属している族の要素の数.

        x: 要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """ 要素 x,y は同一視されているか?

        x,y: 要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """ 要素 x が属している族の要素.
        ※族の要素の個数が欲しいときは size を使うこと!!

        x: 要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def edge_count(self, x):
        """ 要素 x が属する族の辺の本数を求める.

        x: 要素
        """
        return self.edges[self.find(x)]

    def is_tree(self, x):
        """ 要素 x が属する族が木かどうかを判定する.

        x: 要素
        """
        return self.size(x)==self.edges[self.find(x)]+1

    def tree_count(self):
        """ 木になっている属の個数を求める.
        """

        X=0
        for g in self.representative():
            if self.is_tree(g):
                X+=1
        return X

    def representative(self):
        """ 代表元のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """ 族の個数
        """

        return self.__group_number

    def all_group_members(self):
        """ 全ての族の出力
        """
        X={r:[] for r in self.representative()}
        for k in range(self.n):
            X[self.find(k)].append(k)
        return X

    def group_list(self):
        """ 各要素が属している族のリストを出力する.

        """
        return [self.find(x) for x in range(self.n)]

    def refresh(self):
        for i in range(self.n):
            _=self.find(i)

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.representative())

    def __repr__(self):
        return self.__str__()

    def __getitem__(self,index):
        return self.find(index)

    def __setitem__(self,x,y):
        self.union(x,y)

class Tree:
    __slots__=("N", "index", "parent", "__mutable",
            "root", "children", "depth", "tower", "upper_list", "deg", "des_count", "preorder_number",
            "euler_vertex", "euler_edge", "in_time", "out_time")

    def __init__(self,N,index=0):
        """ N 頂点 (index, index+1, ..., N-1+index) の根付き木を生成する. """
        self.N=N
        self.index=index
        self.parent=[-1]*(N+index)
        self.__mutable=True

    def vertex_exist(self,x):
        """ 頂点 x が存在するかどうかを判定する. """

        return self.index<=x<self.index+self.N

    def __after_seal_check(self,*vertexes):
        """ 木が確定していて, vertexes の頂点が存在するかどうかをチェックする. """

        if self.__mutable:
            return False

        for v in vertexes:
            if not self.vertex_exist(v):
                return False
        return True

    def is_mutable(self):
        """ 木が確定して [いない] かどうかを返す. """
        return self.__mutable

    #設定パート
    def root_set(self,root):
        """ 頂点 x を根に設定する."""

        assert self.vertex_exist(root)
        assert self.__mutable

        self.root=root

    def parent_set(self,x,y):
        """ 頂点 x の親を y に設定する."""

        assert self.vertex_exist(x)
        assert self.vertex_exist(y)
        assert self.__mutable

        self.parent[x]=y

    def child_set(self,x,y):
        """ 頂点 x の子の一つに y を設定する."""

        assert self.vertex_exist(x)
        assert self.vertex_exist(y)
        assert self.__mutable

        self.parent[y]=x

    def seal(self):
        """ 木の情報を確定させる."""

        assert self.__mutable
        assert hasattr(self,"root")

        a=self.index
        b=self.index+self.N
        C=[[] for _ in range(b)]

        p=self.parent
        ve=self.vertex_exist
        for i in range(a,b):
            if i!=self.root:
                assert ve(p[i])
                C[p[i]].append(i)

        self.__mutable=False
        self.children=C

    #データを求める.
    def depth_search(self,Mode=True):
        """ 木の深さを求める. """

        assert self.__after_seal_check()

        if hasattr(self,"depth"):
            if Mode:
                return self.depth
            else:
                return

        from collections import deque
        C=self.children
        D=[-1]*(self.index+self.N)
        E=[[] for _ in range(self.N)]

        Q=deque([self.root])
        D[self.root]=0
        E[0]=[self.root]

        while Q:
            x=Q.popleft()
            d=D[x]
            for y in C[x]:
                D[y]=d+1
                E[d+1].append(y)
                Q.append(y)

        self.depth=D
        self.tower=E

        if Mode:
            return D

    def vertex_depth(self,x):
        """ 頂点 x の深さを求める."""

        assert self.__after_seal_check(x)

        if not hasattr(self,"depth"):
            self.depth_search(Mode=False)
        return self.depth[x]

    def __upper_list(self):
        assert self.__after_seal_check()

        if hasattr(self,"upper_list"):
            return

        if not hasattr(self,"depth"):
            self.depth_search(False)

        b=max(self.depth).bit_length()
        X=[[-1]*(self.index+self.N) for _ in range(b)]

        Y=X[0]
        p=self.parent
        rg=range(self.index,self.index+self.N)

        for x in rg:
            if x!=self.root:
                Y[x]=p[x]
            else:
                Y[x]=self.root

        for k in range(1,b):
            Y=X[k-1]
            Z=X[k]

            for x in rg:
                Z[x]=Y[Y[x]]
        self.upper_list=X

    def upper(self,x,k,over=True):
        """ 頂点 x から見て k 個親の頂点を求める.

        over: (頂点 x の深さ)<k のときに True ならば根を返し, False ならばエラーを吐く.
        """

        assert self.__after_seal_check(x)
        assert 0<=k

        if not hasattr(self,"upper_list"):
            self.__upper_list()

        if self.vertex_depth(x)<k:
            if over:
                return self.root
            else:
                raise ValueError

        i=0
        while k:
            if k&1:
                x=self.upper_list[i][x]
            k>>=1
            i+=1
        return x

    def lowest_common_ancestor(self,x,y):
        """ 頂点 x, y の最小共通先祖 (x,yに共通する先祖で最も深いもの) を求める. """

        assert self.__after_seal_check(x,y)

        dd=self.vertex_depth(y)-self.vertex_depth(x)
        if dd<0:
            x,y=y,x
            dd=-dd

        y=self.upper(y,dd)
        if x==self.root:
            return x
        if x==y:
            return x

        d=self.vertex_depth(x)
        b=d.bit_length()

        X=self.upper_list
        for k in range(b-1,-1,-1):
            px=X[k][x];py=X[k][y]
            if px!=py:
                x=px;y=py

        return self.upper(x,1)

    def __degree_count(self):
        assert self.__after_seal_check()

        if hasattr(self,"deg"):
            return

        self.deg=[0]*(self.index+self.N)
        for v in range(self.index,self.index+self.N):
            d=len(self.children[v])+1
            if d==self.root:
                d-=1
            self.deg[v]=d
        return

    def degree(self,v):
        """ 頂点 v の次数を求める. """

        assert self.__after_seal_check(v)

        if not hasattr(self,"deg"):
            self.__degree_count()
        return self.deg[v]

    def diameter(self):
        """ 木の直径を求める."""

        assert self.__after_seal_check()

        from collections import deque
        def bfs(start):
            X=[-1]*(self.index+self.N)
            Q=deque([start])
            X[start]=0

            pa=self.parent
            ch=self.children
            while Q:
                x=Q.popleft()

                if X[pa[x]]==-1:
                    Q.append(pa[x])
                    X[pa[x]]=X[x]+1

                for y in ch[x]:
                    if X[y]==-1:
                        Q.append(y)
                        X[y]=X[x]+1
            y=max(range(self.index,self.index+self.N),key=lambda x:X[x])
            return y,X[y]

        y,_=bfs(self.root)
        z,d=bfs(y)
        return d,(y,z)

    def path(self,u,v):
        """ 頂点 u, v 間のパスを求める. """

        assert self.__after_seal_check(u,v)

        w=self.lowest_common_ancestor(u,v)
        pa=self.parent

        X=[u]
        while u!=w:
            u=pa[u]
            X.append(u)

        Y=[v]
        while v!=w:
            v=pa[v]
            Y.append(v)
        return X+Y[-2::-1]

    def is_parent(self, u, v):
        """ u は v の親か? """

        assert self.__after_seal_check(u,v)
        return v!=self.root and u==self.parent[v]

    def is_children(self, u, v):
        """ u は v の子か? """

        assert self.__after_seal_check(u,v)
        return self.is_parent(v,u)

    def is_brother(self,u,v):
        """ 2つの頂点 u, v は兄弟 (親が同じ) か?  """

        assert self.__after_seal_check(u,v)

        if u==self.root or v==self.root:
            return False
        return self.parent[u]==self.parent[v]

    def is_ancestor(self,u,v):
        """ 頂点 u は頂点 v の先祖か? """

        assert self.__after_seal_check(u,v)

        dd=self.vertex_depth(v)-self.vertex_depth(u)
        if dd<0:
            return False

        v=self.upper(v,dd)
        return u==v

    def is_descendant(self,u,v):
        """ 頂点 u は頂点 v の子孫か? """

        assert self.__after_seal_check(u,v)
        return self.is_ancestor(v,u)

    def direction(self, u, v):
        """ 頂点 u から頂点 v へ向かうパスが頂点 u の次に通る頂点"""

        assert self.__after_seal_check(u,v)
        assert u!=v

        if self.is_ancestor(u,v):
            du=self.vertex_depth(u)
            dv=self.vertex_depth(v)
            return self.upper(v,dv-(du+1))
        else:
            return self.parent[u]

    def is_leaf(self,v):
        """ 頂点 v は葉? """

        return not bool(self.children[v])

    def distance(self,u,v):
        """ 2頂点 u, v 間の距離を求める. """

        assert self.__after_seal_check(u,v)

        dep=self.vertex_depth
        return dep(u)+dep(v)-2*dep(self.lowest_common_ancestor(u,v))

    def __descendant_count(self):
        assert self.__after_seal_check()
        if hasattr(self,"des_count"):
            return

        if not hasattr(self,"tower"):
            self.depth_search(False)

        self.des_count=[1]*(self.index+self.N)
        pa=self.parent
        for T in self.tower[:0:-1]:
            for x in T:
                self.des_count[pa[x]]+=self.des_count[x]
        return

    def descendant_count(self, v):
        """ 頂点 v の子孫の数を求める. """
        assert self.__after_seal_check(v)
        self.__descendant_count()
        return self.des_count[v]

    def subtree_size(self, v):
        """ 頂点 v を根とした部分根付き木のサイズを求める. """
        return self.descendant_count(v)

    def preorder(self,v):
        """ 頂点 v の行きがけ順を求める. """
        assert self.__after_seal_check(v)
        if hasattr(self,"preorder_number"):
            self.preorder_number[v]

        from collections import deque
        Q=deque([self.root])
        T=[-1]*(self.N+self.index)

        p=1
        while Q:
            x=Q.popleft()
            T[x]=p
            p+=1

            C=self.children[x]
            for y in C:
                Q.append(y)
        self.preorder_number=T
        return T[v]

    def dfs_yielder(self, order=None):
        """ DFS における頂点の出入りを yield する.

        以下のような関数を (仮想的に) 実行する.

        def dfs(v):
            yield (v,1) #頂点 v に入る
            for w in self.children[v]:
                dfs(w) #頂点 v を出る.
            yield (v,0)

        order (1変数関数): for w in self.children[v] の順番を指定する (昇順) (※ 無い場合は任意, 破壊的)
        """
        assert self.__after_seal_check()

        #最初
        yield (self.root,1)

        v=self.root

        ch=self.children
        pa=self.parent

        R=[-1]*self.index+[len(ch[x]) for x in range(self.index,self.index+self.N)]
        S=[0]*(self.index+self.N)

        if order!=None:
            for w in range(self.index,self.index+self.N):
                ch[w].sort(key=order)

        while True:
            if R[v]==S[v]:  #もし,進めないならば
                yield (v,0) #頂点vを出る
                if v==self.root:
                    break
                else:
                    v=pa[v]
            else:   #進める
                w=v
                v=ch[v][S[v]]
                S[w]+=1
                yield (v,1)

    def top_down(self):
        """ 木の根から yield する. """

        assert self.__after_seal_check()
        if not hasattr(self,"tower"):
            self.depth_search(False)

        for E in self.tower:
            for v in E:
                yield v

    def bottom_up(self):
        """ 木の葉から yield する. """

        assert self.__after_seal_check()
        if not hasattr(self,"tower"):
            self.depth_search(False)

        for E in self.tower[::-1]:
            for v in E:
                yield v

    def tree_dp_from_leaf(self,merge,unit,f,g,Mode=False):
        """ 葉から木 DP 行う.

        [input]
        merge: 可換モノイドを成す2項演算 M x M -> M
        unit: Mの単位元
        f: X x V x V → M: f(x,v,w): v が親, w が子
        g: M x V → X: g(x,v)
        Mode: False → 根の値のみ, True → 全ての値

        [補足]
        頂点 v の子が x,y,z,...のとき, 更新式は * を merge として
            dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*..., v)
        になる.
        """
        assert self.__after_seal_check()

        data=[unit]*(self.index+self.N)
        ch=self.children

        for x in self.bottom_up():
            for y in ch[x]:
                data[x]=merge(data[x],f(data[y],x,y))
            data[x]=g(data[x],x)

        if Mode:
            return data
        else:
            return data[self.root]

    def tree_dp_from_root(self,f,alpha):
        """ 根から木 DP を行う.

        [input]
        alpha: 初期値
        f: X x V x V → X: f(x,v,w): v が親, w が子

        [補足]
        頂点 v の親が x のとき, 更新式は
            dp[v]=f(dp[x],x,v) (x!=root), alpha (x==root)
        になる.
        """
        assert self.__after_seal_check()

        data=[0]*(self.index+self.N)
        ch=self.children

        data[self.root]=alpha
        for x in self.top_down():
            for y in ch[x]:
                data[y]=f(data[x],x,y)

        return data

    def rerooting(self,merge,unit,f,g):
        """ 全方位木 DP を行う.

        [input]
        merge: 可換モノイドを成す2項演算 M x M -> M
        unit: M の単位元
        f: X x V x V → M: f(x,v,w): v が親, w が子
        g: M x V → X: g(x,v)

        ※ tree_dp_from_leaf と同じ形式

        [補足]
        頂点 v の子が x,y,z,...のとき, 更新式は
        dp[v]=g(f(dp[x],v,x)*f(dp[y],v,y)*f(dp[z],v,z)*..., v)
        になる.
        """
        assert self.__after_seal_check()

        upper=[unit]*(self.index+self.N)
        lower=[unit]*(self.index+self.N)

        ch=self.children
        pa=self.parent

        #DFSパート
        lower=self.tree_dp_from_leaf(merge,unit,f,g,True)

        #BFSパート
        for v in self.top_down():
            cc=ch[v]

            #累積マージ
            deg=len(cc)

            Left=[unit]; x=unit
            for c in cc:
                x=merge(x,f(lower[c],v,c))
                Left.append(x)

            Right=[unit]; y=unit
            for c in cc[::-1]:
                y=merge(y,f(lower[c],v,c))
                Right.append(y)
            Right=Right[::-1]

            for i in range(deg):
                c=cc[i]

                a=merge(Left[i],Right[i+1])

                if v!=self.root:
                    b=merge(a,f(upper[v],v,pa[v]))
                else:
                    b=a

                upper[c]=g(b,v)

        A=[unit]*(self.index+self.N)
        for v in range(self.index,self.index+self.N):
            if v!=self.root:
                a=f(upper[v],v,pa[v])
            else:
                a=unit

            for c in ch[v]:
                a=merge(a,f(lower[c],v,c))
            A[v]=g(a,v)
        return A

    def euler_tour_vertex(self, order=None):
        """ オイラーツアー (vertex) に関する計算を行う.

        order: 頂点の順番を指定する (破壊的)
        """

        assert self.__after_seal_check()
        if hasattr(self,"euler_vertex"):
            return

        #最初
        X=[-1]*(2*self.N-1) #X: Euler Tour (vertex) のリスト

        v=self.root

        ch=self.children
        if order!=None:
            for i in range(self.index,self.index+self.N):
                ch[i].sort(key=order)

        pa=self.parent

        R=[-1]*self.index+[len(ch[x]) for x in range(self.index,self.index+self.N)]
        S=[0]*(self.index+self.N)

        for t in  range(2*self.N-1):
            X[t]=v
            if R[v]==S[v]:
                v=pa[v]
            else:   #進める
                w=v
                v=ch[v][S[v]]
                S[w]+=1

        self.euler_vertex=X
        self.in_time=[-1]*(self.index+self.N)
        self.out_time=[-1]*(self.index+self.N)
        for t in range(2*self.N-1):
            v=X[t]
            if self.in_time[v]==-1:
                self.in_time[v]=self.out_time[v]=t
            else:
                self.out_time[v]=t

    def euler_tour_edge(self):
        """ オイラーツアー (edge) に関する計算を行う.

        (u,v,k): u から v へ向かう (k=+1 のときは葉へ進む向き, k=-1 のときは根へ進む向き)
        """

        assert self.__after_seal_check()
        if hasattr(self,"euler_edge"):
            return

        if not hasattr(self, "euler_vertex"):
            self.euler_tour_vertex()

        self.euler_edge=[0]*(2*(self.N-1))
        euler=self.euler_vertex
        pa=self.parent
        for t in range(2*(self.N-1)):
            u=euler[t]; v=euler[t+1]
            k=1 if u==pa[v] else -1
            self.euler_edge[t]=(u,v,k)

    def centroid(self, all=False):
        """ 木の重心を求める

        all: False → 重心のうちの1頂点. True → 全ての重心.
        """

        assert self.__after_seal_check()

        M=self.N//2

        if not hasattr(self,"des_count"):
            self.__descendant_count()

        G=[]; ch=self.children; des=self.des_count

        for v in range(self.index, self.index+self.N):
            if self.N-des[v]>M:
                break

            flag=1
            for x in ch[v]:
                if des[x]>M:
                    flag=0
                    break
            if flag:
                if all:
                    G.append(v)
                else:
                    return v
        return G

    def generated_subtree(self,S):
        """ S を含む最小の部分木の頂点を求める. """
        assert self.__after_seal_check(*S)

        if not hasattr(self, "in_time"):
            self.euler_tour_vertex()

        S=sorted(set(S),key=lambda i:self.in_time[i])
        K=len(S)

        T=set()
        for i in range(K-1):
            for a in self.path(S[i],S[i+1]):
                T.add(a)
        return sorted(T)

    def generated_subtree_size(self,S):
        """ S を含む最小の部分木のサイズを求める. """
        assert self.__after_seal_check(*S)

        if not hasattr(self, "in_time"):
            self.euler_tour_vertex()

        S=sorted(set(S),key=lambda i:self.in_time[i])
        K=len(S)

        X=0
        for i in range(K-1):
            X+=self.distance(S[i],S[i+1])
        return (X+self.distance(S[-1],S[0]))//2

def Spanning_Tree(N,E,root,index=0,exclude=False):
    """ 連結なグラフから全域木をつくる.

    N: 頂点数
    E:  辺のリスト
    root: 根
    exclude: 全域木から外れた辺のリストを出力するか.
    """

    from collections import deque
    F=[set() for _ in range(index+N)]
    EE=[]
    L=[]
    for u,v in E:
        assert index<=u<index+N
        assert index<=v<index+N

        if (u==v) or (u in F[v]):
            L.append((u,v))
            continue

        EE.append((u,v))
        F[u].add(v)
        F[v].add(u)

    X=[-1]*(index+N)
    X[root]=root

    C=[[] for _ in range(index+N)]

    Q=deque([root])
    while Q:
        x=Q.popleft()
        for y in F[x]:
            if X[y]==-1:
                X[y]=x
                Q.append(y)
                C[x].append(y)

    T=Tree(N,index)
    T.root_set(root)
    T.parent=X
    T.children=C
    T.seal()

    if exclude==False:
        return T

    pa=T.parent
    for u,v in EE:
        if not(pa[v]==u or pa[u]==v):
            L.append((u,v))

    return T,L

#==================================================
import sys
from collections import deque
from operator import add

input=sys.stdin.readline
write=sys.stdout.write

# 情報読み取り & 連結成分を求める.
N,M,Q=map(int,input().split())

U=Union_Find(N+1)
E=[]
for _ in range(M):
    u,v=map(int,input().split())

    U.union(u,v)
    E.append((u,v))

# 連結成分をサイクルで結ぶ.
R=U.representative()
del R[R.index(0)]

if len(R)>=2:
    for k in range(len(R)-1):
        E.append((R[k],R[k+1]))
    E.append((R[-1],R[0]))

root=1
T,L=Spanning_Tree(N,E,root,root,True)

# 全域木から外れた辺のパスを求める ... サイクル基底を求める.
Y=[0]*(N+1)
for a,b in L:
    c=T.lowest_common_ancestor(a,b)
    Y[a]+=1; Y[b]+=1; Y[c]-=2

f=lambda x,v,w: x
g=lambda x,v: x+Y[v]

X=T.tree_dp_from_leaf(add,0,f,g,True)

# サイクルを取り除く& 連結成分を求める.
V=Union_Find(N+1)
for v in range(1,N+1):
    if v!=root and X[v]==0:
        V.union(v,T.parent[v])

Id=V.group_list()
# クエリに答える
Ans=[""]*Q
for q in range(Q):
    x,y=map(int,input().split())
    Ans[q]="Yes" if Id[x]==Id[y] else "No"

write("\n".join(Ans))
0