Basic implementation of union-find data structure

unionfind.py

#!/usr/bin/python3

class Node(object):
    def __init__(self, value, successor, item):
        self.value = value
        self.successor = successor
        self.item = item

class Item(object):
    def __init__(self, head, tail):
        self.head = head
        self.tail = tail

    def size(self):
        current = self.head
        counter = 0
        while current is not None:
            counter += 1
            current = current.successor
        return counter

class UnionSet(object):
    def __init__(self):
        self.items = dict()

    def makeset(self, x):
        node = Node(x, None, None)
        item = Item(node, node)
        node.item = item
        self.items[x] = node

    def find(self, x):
        if x in self.items:
            return self.items[x].item
        else:
            return None

    def union(self, a, b):
        current = b.head
        while current is not None:
            current.item = a
            current = current.successor
        a.tail.successor = b.head
        a.tail = b.tail
        return a

tn = int(input())
for t in range(1, tn+1):
    a, b, c = [int(k) for k in input().split()]
    wealth = [int(k) for k in input().split()]
    married = set()

    relations = UnionSet()
    for x in range(1,a+1):
        relations.makeset(x)

    for _ in range(b):
        x, y = [relations.find(int(k)) for k in input().split()]
        relations.union(x, y)

    for _ in range(c):
        xi, yi = [int(k) for k in input().split()]
        married.add(xi)
        married.add(yi)
        x, y = relations.find(xi), relations.find(yi)
        relations.union(x, y)

    own_family = relations.find(a)
    non_family = [k for k in range(1, a+1) if relations.items[k].item != own_family and k not in married]
    if non_family:
        print('Case %d: %d' % (t, max(wealth[k-1] for k in non_family)))
    else:
        print('Case %d: impossible' % t)