Given a connected undirected graph GGG consisting of nnn vertices and mmm edges, with each edge has a positive integer weight wiw_iwi .In one operation, you can choose an edge and change its weight to any positive integer.We define a spanning tree TTT of GGG is an xxx-spanning treeif the gcd of the weights of all the edges in TTTis a multiple ofthe given number xxx .Colin wants to ask you that at least how many operations have been executed, there exists at least one xxx-spanning treeTTT of GGG .For some secret reason there will be kkk independent queries, please note that every query is based on the initially given graph GGG .Recall that the spanning treeTTT of the graph GGG is a subgraph which is a tree and contains all vertices of the graph GGG. In other words, it is a connected graph which contains n1n-1n1 edges and can be obtained by removing some of the edges from GGG.
Given a connected undirected graph GGG consisting of nnn vertices and mmm edges, with each edge has a positive integer weight wiw_iwi . In one operation, you can choose an edge and change its weight to any positive integer. We define a spanning tree TTT of GGG is an xxx-spanning tree if the gcd (greatest common divisior) of the weights of all the edges in TTT is a multiple of the given number xxx (i.e. xxx is a divisor of the gcd) . Colin wants to ask you that at least how many operations have been executed, there exists at least one xxx-spanning tree TTT of GGG . For some secret reason there will be kkk independent queries, please note that every query is based on the initially given graph GGG (i.e. all operations of your answer have not been actually executed) . Recall that the spanning tree TTT of the graph GGG is a subgraph which is a tree and contains all vertices of the graph GGG. In other words, it is a connected graph which contains n − 1n - 1n − 1 edges and can be obtained by removing some of the edges from GGG.
