student.py

from collections import defaultdict


def dfs(graph, start, end, path=[]):
    has_choice = False
    for i in graph[start]:
        if len(path) % 2 == 1 and i in path and i != path[-1]:
            return None
        if i == end:
            yield [start, i]
            has_choice = True
            continue
        if i in path:
            continue
        p = dfs(graph, i, end, path + [start])
        if p is not None:
            p = list(p)
            if len(p) > 0:
                has_choice = True
                for j in p:
                    yield [start] + j
            elif len(path) % 2 == 1:
                return None
        elif len(path) % 2 == 1:
            return None
    if not has_choice:
        return None


c = int(input())
for i in range(c):
    n, m, s, t = map(int, input().split())
    edges = []
    for j in range(m):
        edges.append(list(map(int, input().split())))

    G = defaultdict(list)
    for (a, b) in edges:
        G[a].append(b)
        G[b].append(a)

    all_paths = list(dfs(G, s, t))
    if len(all_paths) == 0:
        print(-1)
    else:
        all_paths.sort(key=lambda l: len(l))
        best = len(all_paths[0])
        print(best // 2 + best % 2)