class Graph: def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]): self.n = n self.directed = directed self.decrement = decrement self.destroy = destroy self.edges = [set() for _ in range(self.n)] self.parent = [-1]*self.n for x, y in edges: self.add_edge(x,y) def add_edge(self, x, y): if self.decrement: x -= 1 y -= 1 self.edges[x].add(y) if self.directed == False: self.edges[y].add(x) def add_adjacent_list(self, i, adjacent_list): if self.decrement: self.edges[i] = set(map(lambda x: x - 1, adjacent_list)) else: self.edges[i] = set(adjacent_list) def bfs(self, start=None, goal=-1, time=0, save=False): """ :param start: スタート地点 :param goal: ゴール地点 :param save: True = 前回の探索結果を保持する :return: (ループがあっても)最短距離。存在しなければ -1 """ if start is None: start=self.decrement start,goal=start-self.decrement,goal-self.decrement if not save: self.parent = [-1] * self.n p, t = start, time self.parent[p] = -2 next_set = deque([(p, t)]) if p==goal: return t while next_set: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ continue if q == goal: self.parent[q]=p return t + 1 self.parent[q] = p next_set.append((q, t + 1)) return -1 def connection_counter(self): """ :return: 連結成分の個数。有効グラフではあまり意味がない。 """ cnt = 0 self.parent = [-1] * self.n for start in range(self.n): if self.parent[start] == -1: cnt += 1 self.bfs(start + self.decrement, save=True) return cnt def connection_detail(self): """ :return: 連結成分の(頂点数, 辺の数)。有効グラフではあまり意味がない。 備考: 木であるための必要十分条件は M=N-1 """ ver_edge=[] self.parent = [-1] * self.n for start in range(self.n): if self.parent[start] == -1: ver_cnt, edge_cnt = self._detail(start + self.decrement) ver_edge.append((ver_cnt, edge_cnt)) return ver_edge def _detail(self, start=None): """ :param start: スタート地点 :param save: True = 前回の探索結果を保持する """ if start is None: start=self.decrement start=start-self.decrement p, t = start, 0 self.parent[p] = -2 next_set = deque([(p, t)]) sub_edges,sub_vers = set(),set() while next_set: p, t = next_set.popleft() sub_vers.add(p) for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue sub_edges.add((min(p,q),max(p,q))) if self.parent[q] != -1: """ サイクル時の処理 """ continue self.parent[q] = p next_set.append((q, t + 1)) return len(sub_vers),len(sub_edges) def distance_list(self, start=None, save=False): """ :param start: スタート地点 :return: スタート地点から各点への距離のリスト ※ 距離無限大が -1 になっている点に注意!!! """ dist = [-1]*self.n if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n p, t = start, 0 self.parent[p] = -2 dist[p] = 0 next_set = deque([(p, t)]) while next_set: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ continue dist[q] = t + 1 self.parent[q] = p next_set.append((q, t + 1)) return dist def parent_list(self, start=None): """ :return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号 訪問しない場合は -1 を返す """ if start is None: start=self.decrement self.distance_list(start) return list(p + self.decrement for p in self.parent[1:]) def most_distant_point(self, start=None, save=False): """ 計算量 O(N) :return: (start から最も遠い頂点, 距離) """ if not save: self.parent = [-1] * self.n if start is None: start=self.decrement start=start-self.decrement res = (start, 0) temp = 0 for i, dist in enumerate(self.distance_list(start+self.decrement, save=save)): if dist > temp: temp = dist res = (i + self.decrement, dist) return res def diameter(self, save=False): """ 計算量 O(N) :return: 木の直径(最も離れた二頂点間の距離)を返す """ if not save: self.parent = [-1] * self.n p = self.most_distant_point(save=save) res = self.most_distant_point(start=p[0], save=save) return res[1] def all_cycle(self): """ 無向グラフ用 O(V(V+E)) """ res=[] for start in range(self.n): flg=0 self.parent = [-1] * self.n p, t = start, 0 self.parent[p] = -2 next_set=deque() starts=set() for q in self.edges[p]: next_set.append((q, t)) self.parent[q]=p starts.add(q) while next_set and flg==0: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ if q in starts: cycle=[q+self.decrement] r=p while r not in starts: cycle.append(r+self.decrement) r=self.parent[r] if r<0: return -1 cycle.append(r+self.decrement) cycle.append(start+self.decrement) res.append(cycle[::-1]) flg=1 break continue self.parent[q] = p next_set.append((q, t + 1)) return res def minimum_cycle_directed(self): """ 有向グラフ用 O(V(V+E)) """ INF=10**18 dist=[] history=[] for i in range(self.n): dist.append(self.distance_list(start=i+self.decrement,save=False,INF=INF)[:]) history.append(self.parent[:]) res=INF s,g=None,None for i in range(self.n): for j in self.edges[i]: if dist[j][i]+1=INF: return [] else: self.parent=history[g] return self.path_restoring(g+self.decrement,s+self.decrement) def dfs(self, start=None, goal=-1, time=0, save=False): """ :param start: スタート地点 :param goal: ゴール地点 :param save: True = 前回の探索結果を保持する :return: ゴール地点までの距離。存在しなければ -1。ループがある時は最短距離とは限らないため注意。 """ if start is None: start=self.decrement start,goal=start-self.decrement,goal-self.decrement if not save: self.parent = [-1] * self.n if self.destroy: edges2 = self.edges else: edges2 = [self.edges[p].copy() for p in range(self.n)] parent,directed=self.parent,self.directed p, t = start, time parent[p] = -2 if p==goal: return t while True: if edges2[p]: q = edges2[p].pop() if q == parent[p] and not directed: """ 逆流した時の処理 """ continue if parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ continue if q == goal: """ ゴール時の処理""" parent[q]=p return t + 1 """ p から q への引継ぎ""" parent[q] = p p, t = q, t + 1 else: """ p から進める点がもう無い時の点 p における処理 """ if p == start and t == time: break p, t = parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ return -1 def cycle_detector(self, start=None, time=0, save=False): """ :param p: スタート地点 :param save: True = 前回の探索結果を保持する(遅い) :return: サイクルリストを返す。存在しない場合は [] """ if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n self.finished=[0]*self.n if self.destroy: edges2 = self.edges else: edges2 = [self.edges[p].copy() for p in range(self.n)] p, t = start, time self.parent[p] = -2 history = [p+self.decrement] cycle = [] while True: if edges2[p]: q = edges2[p].pop() if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ """""""""""""""""""" continue if self.parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ if not self.finished[q] and not cycle: cycle_start=history.index(q+self.decrement) if save==False: return history[cycle_start:] else: cycle = history[cycle_start:] """""""""""""""""""" continue """ p から q への引継ぎ""" """""""""""""""""""" history.append(q+self.decrement) self.parent[q] = p p, t = q, t + 1 else: """ p から進める点がもう無い時の点 p における処理 """ self.finished[p]=1 history.pop() """""""""""""""""""" if p == start and t == time: break p, t = self.parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ """""""""""""""""""" return cycle def tree_counter(self, detail=False): """ :param detail: True = サイクルのリストを返す :return: 木(閉路を含まない)の個数を返す """ self.destroy=True # これをしないと計算量が壊れる self.parent = [-1] * self.n self.finished=[0]*self.n connection_number = 0 cycle_list = [] for p in range(self.n): if self.parent[p] == -1: connection_number += 1 cycle = self.cycle_detector(p + self.decrement, save=True) if cycle: cycle_list.append(cycle) if not detail: return connection_number - len(cycle_list) else: return cycle_list def path_detector(self, start=None, time=0, save=False): """ :param p: スタート地点 :param save: True = 前回の探索結果を保持する :return: 各点までの距離と何番目に発見したかを返す """ if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n edges2= [] for i in range(self.n): edges2.append(sorted(self.edges[i], reverse=True)) p, t = start, time self.parent[p] = -2 full_path = [(p + self.decrement,t)] while True: if edges2[p]: q = edges2[p].pop() if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ """""""""""""""""""" continue if self.parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ """""""""""""""""""" continue """ p から q への引継ぎ""" """""""""""""""""""" self.parent[q] = p p, t = q, t + 1 full_path.append((p + self.decrement, t)) else: """ p から進める点がもう無い時の点 p における処理 """ """""""""""""""""""" if p == start and t == time: break p, t = self.parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ full_path.append((p + self.decrement, t)) """""""""""""""""""" return full_path def path_restoring(self,start,goal): start,goal=start-self.decrement,goal-self.decrement q=goal res=[] while q!=start: res.append(q+self.decrement) q=self.parent[q] if q<0: return -1 res.append(start+self.decrement) return res[::-1] def draw(self): """ :return: グラフを可視化 """ import matplotlib.pyplot as plt import networkx as nx if self.directed: G = nx.DiGraph() else: G = nx.Graph() for x in range(self.n): for y in self.edges[x]: G.add_edge(x + self.decrement, y + self.decrement) pos = nx.spring_layout(G) nx.draw_networkx(G, pos, connectionstyle='arc3, rad = 0.1') plt.axis("off") plt.show() ################################################################################################## def make_graph(N_min=2, N_max=5, M_min=1, M_max=10, directed=False,decrement=True): """ 自己ループの無いグラフを生成。N>=2 :param directed: True = 有効グラフ :param decrement: True = 1-indexed :return: """ import random input_data = [] global input N=random.randint(N_min,N_max,) if N>2: M_max2=(3*N-6)*(1+directed) else: M_max2=1 M=random.randint(max(1,M_min),min(M_max,M_max2)) print("#########") edges=set() for _ in range(1,M+1): edge=random.sample(range(decrement,N+decrement),2) if directed==False: edge.sort() edge=tuple(edge) if edge not in edges: edges.add(edge) print(N,len(edges)) input_data.append(" ".join(map(str,(N,len(edges))))) for edge in edges: print(*edge) input_data.append(" ".join(map(str,edge))) print("#########") input_data=iter(input_data) input = lambda: next(input_data) def draw(N,edges,decrement=1): import matplotlib.pyplot as plt import networkx as nx G=nx.Graph() for x in range(N): for y in edges[x]: G.add_edge(x+decrement,y+decrement) pos=nx.spring_layout(G) nx.draw_networkx(G,pos) plt.axis("off") plt.show() class UnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): """ 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)""" tmp = [] parents = self.parents while parents[x] >= 0: tmp.append(x) x = parents[x] for y in tmp: parents[y] = x return x def union(self, x, y): """ 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。""" x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def same(self, x, y): """ xとyが同じ根の子かを判定 """ return self.find(x) == self.find(y) def size(self, x): """ xの根のparent(= 要素数)を返す """ return -self.parents[self.find(x)] def members(self, x): """ xが属するグループの要素をリストとして返す O(N)""" root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): """ 全ての根の要素をリストとして返す O(N)""" return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): """ グループの数を返す O(N)""" return len(self.roots()) def size_list(self): """ 各グループの要素数のリストを返す(根の番号は返さない) O(N)""" return [-x for x in self.parents if x < 0] def all_group_members(self): """ {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)""" res = [[] for _ in range(self.n)] for i in range(self.n): x = self.find(i) res[x].append(i) return {r: res[r] for r in self.roots()} def __str__(self): return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) ###################################################################### def example_tree(N=10,show=True,decrement=1): global input # decrement=True: create 1-indexed tree def find(x): tmp=[] while parents[x]>=0: tmp.append(x) x=parents[x] for y in tmp: parents[y]=x return x def union(x,y): x,y=find(x),find(y) if x==y: return if parents[x]>parents[y]: x,y=y,x parents[x]+=parents[y] parents[y]=x def same(x,y): return find(x)==find(y) import random # N = random.randint(2, N) parents=[-1]*N edges=[] input_data=[] input_data.append(str(N)) for i in range(N-1): while True: j=random.randint(0,N-1) if same(i,j): continue union(i,j) edges.append((i+decrement,j+decrement)) break for i,j in edges: input_data.append(" ".join(map(str,(i,j)))) input_data=iter(input_data) input=lambda:next(input_data) if show: print("#######################") print(N) for p in edges: print(*p) print("#######################") return edges def example_special_tree(N, type, show=True, decrement=1): global input edges = [] if type=="path": for i in range(N-1): edges.append((i+decrement,i+1+decrement)) if type=="star": for i in range(N-1): edges.append((i,i+1+decrement)) if type=="binary": i = 1 while True: if (i<<1) >= N: break edges.append((i-1+decrement, (i<<1)-1+decrement)) if (i<<1)+1 >= N: break edges.append((i-1+decrement, (i<<1)+decrement)) i += 1 input_data=[] input_data.append(str(N)) for i,j in edges: input_data.append(" ".join(map(str,(i,j)))) input_data=iter(input_data) input=lambda:next(input_data) if show: print("#######################") print(N) for p in edges: print(*p) print("#######################") return edges def example(): global input example=iter( """ 6 9 1 2 2 3 3 4 4 5 5 6 5 1 5 2 6 1 6 2 """ .strip().split("\n")) input=lambda:next(example) ###################################################################### import sys input=sys.stdin.readline from collections import deque # example() # make_graph(N_min=7,N_max=7,M_min=10,M_max=10,directed=True) N, M = map(int, input().split()) G = Graph(N, directed=False, decrement=True, destroy=False) U = UnionFind(N) for _ in range(M): x, y = map(int, input().split()) G.add_edge(x, y) U.union(x-1, y-1) Q=int(input()) for _ in range(Q): a=int(input()) p, dist = G.most_distant_point(start=a) if dist==0: print(0,0) else: k=(dist-1).bit_length() print(U.size(a-1)-1, k)