CF723F st-Spanning Tree

You are given an undirected connected graph consisting of $ n $ vertices and $ m $ edges. There are no loops and no multiple edges in the graph. You are also given two distinct vertices $ s $ and $ t $ , and two values $ d_{s} $ and $ d_{t} $ . Your task is to build any spanning tree of the given graph (note that the graph is not weighted), such that the degree of the vertex $ s $ doesn't exceed $ d_{s} $ , and the degree of the vertex $ t $ doesn't exceed $ d_{t} $ , or determine, that there is no such spanning tree. The spanning tree of the graph $ G $ is a subgraph which is a tree and contains all vertices of the graph $ G $ . In other words, it is a connected graph which contains $ n-1 $ edges and can be obtained by removing some of the edges from $ G $ . The degree of a vertex is the number of edges incident to this vertex.

N/A

N/A