# Idea
In the world of graphs exists a structure called "spanning tree". It is unique because it's created not on its own, but based on other graphs. To make a spanning tree out of a given graph you should remove all the edges which create cycles, for example:
```
This can become      this      or      this        or       this
 A                    A                  A                   A
 |\                   |                   \                  |\
 | \       ==>        |                    \                 | \
 |__\                 |__                 __\                |  \
B   C                 B  C               B  C                B  C
```
Each *edge* (line between 2 *vertices*, i.e. points) has a weight, based on which you can build minimum and maximum spanning trees (sum of weights of vertices in the resulting tree is minimal/maximal possible).  
[Wikipedia article](https://en.wikipedia.org/wiki/Spanning_tree) on spanning trees, in case you need it.
___
# Task
You will receive an array like this: `[["AB", 2], ["BC", 4], ["AC", 1]]` which includes all edges of an arbitrary graph and a string `"min"`/`"max"`. Based on them you should get and return a new array which includes only those edges which form a minimum/maximum spanning trees.
```python
edges = [("AB", 2), ("BC", 4), ("AC", 1)]
make_spanning_tree(edges, "min")    ==>    [("AB", 2), ("AC", 1)]
make_spanning_tree(edges, "max")    ==>    [("AB", 2), ("BC", 4)]
```
___
# Notes
* All vertices will be connected with each other
* You may receive cycles, for example - `["AA", n]`
* The subject of the test are these 3 values: number of vertices included, total weight, number of edges, but **you should not return them**, there's a special function which will analyze your output instead
class DisjointSet:
    def __init__(self):
        self.data = {}
        
    def add_node(self, v):
        self.data[v] = v
        
    def find(self, v):
        if (self.data[v] == v):
            return v
        else :
            return self.find(self.data[v])
        
    def union(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        self.data[root_v] = root_w
        
    def in_same_set(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        return root_v == root_w

def make_spanning_tree(edges, t):
    if (t == 'min'):
        edges = sorted(edges, key=lambda x: x[1])    
    elif (t == 'max'):
        edges = sorted(edges, key=lambda x: -x[1])
        
    
    tree = DisjointSet()
    for edge in edges:
        v, w = edge[0][0], edge[0][1]
        if (v not in tree.data.keys()):
            tree.add_node(v)
        if (w not in tree.data.keys()):
            tree.add_node(w)
    cnt = 0
    output = []
    while (cnt < len(tree.data)-1):
        edge = edges.pop(0)
        v, w = edge[0][0], edge[0][1]
        
        if (not tree.in_same_set(v, w)):
            tree.union(v, w)
            output.append(edge)
            cnt += 1
            
    return output
class DisjointSet:
    def __init__(self):
        self.data = {}
        
    def add_node(self, v):
        self.data[v] = v
        
    def find(self, v):
        if (self.data[v] == v):
            return v
        else :
            return self.find(self.data[v])
        
    def union(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        self.data[root_v] = root_w
        
    def in_same_set(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        return root_v == root_w

def make_spanning_tree(edges, t):
    if (t == 'min'):
        edges = sorted(edges, key=lambda x: x[1])    
    elif (t == 'max'):
        edges = sorted(edges, key=lambda x: -x[1])
        
    
    tree = DisjointSet()
    for edge in edges:
        v, w = edge[0][0], edge[0][1]
        if (v not in tree.data.keys()):
            tree.add_node(v)
        if (w not in tree.data.keys()):
            tree.add_node(w)
    cnt = 0
    output = []
    while (cnt < len(tree.data)-1):
        edge = edges.pop(0)
        v, w = edge[0][0], edge[0][1]
        
        if (not tree.in_same_set(v, w)):
            tree.union(v, w)
            output.append(edge)
            cnt += 1
            
    return output