Complete Mirror
You have given tree consist of $$$n$$$ vertices. Select a vertex as root vertex that satisfies the condition below.  For all vertices $$$v_{1}$$$ and $$$v_{2}$$$, if $$$distance$$$($$$root$$$, $$$v_{1}$$$) $$$= distance$$$($$$root$$$, $$$v_{2})$$$ then $$$degree$$$($$$v_{1}$$$) $$$= degree$$$($$$v_{2}$$$), where $$$degree$$$ means the number of vertices connected to that vertex, and $$$distance$$$ means the number of edges between two vertices. Determine and find if there is such root vertex in the tree. If there are multiple answers, find any of them.
This is the picture for the first example. $$$1$$$, $$$5$$$, $$$7$$$ also can be a valid answer.  This is the picture for the second example. You can see that it's impossible to find such root vertex.  
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the number of vertices.Each of the next $$$n-1$$$ lines contains two integers $$$v_{i}$$$ and $$$u_{i}$$$ ($$$1 \le v_{i} \lt u_{i} \le n$$$) — it means there is an edge exist between $$$v_{i}$$$ and $$$u_{i}$$$. It is guaranteed that the graph forms tree.
If there is such root vertex exists, print any of them. Otherwise, print $$$-1$$$.
def longest_path():
    try:
        d = [-1 for _ in range(n)]
        d[0] = 0
        q = [0]
        for i in range(n):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    q.append(t)
                    d[t] = d[f] + 1
        u = q[-1]
        d = [-1 for _ in range(n)]
        p = [-1 for _ in range(n)]
        d[u] = 0
        q = [u]
        for i in range(n):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    q.append(t)
                    d[t] = d[f] + 1
                    p[t] = f
        v = q[-1]
        ld = d[v]
        w = v
        if ld & 1:
            return (u, v, None)
        while d[w] != ld >> 1:
            w = p[w]
        return (u, v, w)
    except:
        print(f'Error raised in longest_path()')

def top(u):
    try:
        if u is None:
            return False
        dist = [-1 for _ in range(n)]
        deg = [-1 for _ in range(n)]
        dist[u] = 0
        q = [u]
        for i in range(n):
            f = q[i]
            if deg[dist[f]] == -1:
                deg[dist[f]] = len(g[f])
            elif len(g[f]) != deg[dist[f]]:
                return False
            for t in g[f]:
                if dist[t] == -1:
                    q.append(t)
                    dist[t] = dist[f] + 1
        return True
    except:
        print(f'Error raised in top({u})')

def semitop(w):
    try:
        if w is None:
            return (False, None)
        d = [-1 for _ in range(n)]
        d[w] = 0
        q = [w]
        i = 0
        while i < len(q):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    if len(g[t]) != 2:
                        d[t] = 100500
                        if top(t):
                            return (True, t)
                    else:
                        d[t] = d[f] + 1
                        q.append(t)
            i += 1
        return (False, None)
    except:
        print(f'Error raised in semitop({w})')
try:
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = map(lambda _: int(_) - 1, input().split())
        g[u].append(v)
        g[v].append(u)
    (u, v, w) = longest_path()
    if top(u):
        print(u + 1)
    elif top(v):
        print(v + 1)
    elif top(w):
        print(w + 1)
    else:
        (k, t) = semitop(w)
        if k:
            print(t + 1)
        else:
            print(-1)
except:
    print(f'Error raised in main')
from collections import deque
n = int(input())
e = [[] for i in range(n + 1)]
for i in range(n - 1):
    (u, v) = map(int, input().split())
    e[u].append(v)
    e[v].append(u)
dep = [-1] * (n + 1)
dep[1] = 0
q = deque([1])
cur = 1
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
dep = [-1] * (n + 1)
pred = [0] * (n + 1)
dep[cur] = 0
q = deque([cur])
end = cur
while q:
    end = q.popleft()
    for to in e[end]:
        if dep[to] == -1:
            dep[to] = dep[end] + 1
            pred[to] = end
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(cur)
    exit()
center = end
for i in range(dep[end] // 2):
    center = pred[center]
dep = [-1] * (n + 1)
dep[end] = 0
q = deque([end])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(end)
    exit()
top = center
dep = [-1] * (n + 1)
dep[center] = 0
q = deque([center])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            if len(e[to]) == 2:
                dep[to] = dep[cur] + 1
                q.append(to)
            elif len(e[to]) == 1:
                top = to
                q.clear()
                break
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(center)
    exit()
dep = [-1] * (n + 1)
dep[top] = 0
q = deque([top])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(top)
    exit()
print(-1)
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
    return (q, dist)

def ok(dist):
    c = [0] * (n + 1)
    for i in range(1, n + 1):
        j = dist[i]
        if not c[j]:
            c[j] = s0[i + 1] - s0[i]
        if c[j] ^ s0[i + 1] - s0[i]:
            return False
    return True
n = int(input())
if n == 1:
    ans = 1
    print(ans)
    exit()
(G, s0) = make_graph(n, n - 1)
inf = pow(10, 9) + 1
(_, du) = bfs(1)
v = du.index(max(du[1:]))
(_, dv) = bfs(v)
u = dv.index(max(dv[1:]))
(_, du) = bfs(u)
ans = -1
if ok(du):
    ans = u
elif ok(dv):
    ans = v
else:
    w = 0
    for i in range(1, n + 1):
        if 2 * du[i] == 2 * dv[i] == du[v]:
            w = i
    if w:
        (p, dw) = bfs(w)
        if ok(dw):
            ans = w
        cnt = [1] * (n + 1)
        cnt[0] = inf
        for i in p[::-1]:
            for v in range(s0[i], s0[i + 1]):
                j = G[v]
                if dw[i] < dw[j]:
                    cnt[i] += cnt[j]
        (w, i) = (0, w)
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if cnt[j] < cnt[w]:
                w = j
        f = 1
        while f:
            f = 0
            for v in range(s0[w], s0[w + 1]):
                j = G[v]
                if dw[w] < dw[j]:
                    w = j
                    f = 1
                    break
        (_, dw) = bfs(w)
        if ok(dw):
            ans = w
print(ans)