There is an undirected tree of $n$ vertices, connected by $n-1$ bidirectional edges. There is also a snake stuck inside of this tree. Its head is at vertex $a$ and its tail is at vertex $b$. The snake's body occupies all vertices on the unique simple path between $a$ and $b$.

The snake wants to know if it can reverse itself  — that is, to move its head to where its tail started, and its tail to where its head started. Unfortunately, the snake's movements are restricted to the tree's structure.

In an operation, the snake can move its head to an adjacent vertex not currently occupied by the snake. When it does this, the tail moves one vertex closer to the head, so that the length of the snake remains unchanged. Similarly, the snake can also move its tail to an adjacent vertex not currently occupied by the snake. When it does this, the head moves one unit closer to the tail. [Image] Let's denote a snake position by $(h,t)$, where $h$ is the index of the vertex with the snake's head, $t$ is the index of the vertex with the snake's tail. This snake can reverse itself with the movements $(4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)$. 

Determine if it is possible to reverse the snake with some sequence of operations.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 100$)  — the number of test cases. The next lines contain descriptions of test cases.

The first line of each test case contains three integers $n,a,b$ ($2\le n\le 10^5,1\le a,b\le n,a\ne b$).

Each of the next $n-1$ lines contains two integers $u_i,v_i$ ($1\le u_i,v_i\le n,u_i\ne v_i$), indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.


-----Output-----

For each test case, output "YES" if it is possible for the snake to reverse itself, or "NO" otherwise.


-----Example-----
Input
4
8 4 7
1 2
2 3
1 4
4 5
4 6
1 7
7 8
4 3 2
4 3
1 2
2 3
9 3 5
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
16 15 12
1 2
2 3
1 4
4 5
5 6
6 7
4 8
8 9
8 10
10 11
11 12
11 13
13 14
10 15
15 16

Output
YES
NO
NO
YES



-----Note-----

The first test case is pictured above.

In the second test case, the tree is a path. We can show that the snake cannot reverse itself.

In the third test case, we can show that the snake cannot reverse itself.

In the fourth test case, an example solution is:

$(15,12)\to (16,11)\to (15,13)\to (10,14)\to (8,13)\to (4,11)\to (1,10)$

$\to (2,8)\to (3,4)\to (2,5)\to (1,6)\to (4,7)\to (8,6)\to (10,5)$

$\to (11,4)\to (13,8)\to (14,10)\to (13,15)\to (11,16)\to (12,15)$.

Difficulty: competition

Starter code:

Solutions:
from sys import stdin
import itertools
input = stdin.readline
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list([int(x) - 1 for x in input().split()])
def getstr(): return input()[:-1]


def solve():
    n, a, b = getint1()
    n += 1
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = getint1()
        adj[u].append(v)
        adj[v].append(u)
    # dfs 1
    max_child = [[-1] * 3 for _ in range(n)]
    stack = [(a, -1, 1)]  # (node, parent)
    while stack:
        u, p, flag = stack.pop()
        if p != -1 and len(adj[u]) < 2:
            max_child[u][0] = 1
            continue
        if flag == 1:
            stack.append((u, p, 0))
            for v in adj[u]:
                if v == p:
                    continue
                stack.append((v, u, 1))
        else:
            for v in adj[u]:
                if v == p:
                    continue
                len_v = max_child[v][0] + 1
                if len_v > max_child[u][0]:
                    max_child[u][2] = max_child[u][1]
                    max_child[u][1] = max_child[u][0]
                    max_child[u][0] = len_v
                elif len_v > max_child[u][1]:
                    max_child[u][2] = max_child[u][1]
                    max_child[u][1] = len_v
                elif len_v > max_child[u][2]:
                    max_child[u][2] = len_v
    # end of dfs 1
    # dfs 2
    body = []
    ret = [False] * n
    max_parent = [-1] * n
    stack.clear()
    stack = [(a, -1, 0)]  # (node, parent, max len from parent)
    while stack:
        u, p, mxp = stack.pop()
        if mxp >= 0:
            stack.append((u, p, -1))
            if p != -1 and len(adj[u]) < 2:
                continue
            max_parent[u] = mxp + 1
            chlen = [max_parent[u], -3]
            for v in adj[u]:
                if v == p:
                    continue
                len_v = max_child[v][0] + 1
                if len_v > chlen[0]:
                    chlen[1] = chlen[0]
                    chlen[0] = len_v
                elif len_v > chlen[1]:
                    chlen[1] = len_v
            for v in adj[u]:
                if v == p:
                    continue
                stack.append(
                    (v, u, chlen[int(max_child[v][0] + 1 == chlen[0])]))
        else:
            is_body = (u == b)
            if not is_body:
                for v in adj[u]:
                    if v != p and ret[v]:
                        is_body = True
                        break
            if is_body:
                body.append(u)
            ret[u] = is_body
    del ret
    # end of dfs2
    ok = False
    body_len = len(body)
    can_turn = [False] * n
    for i in range(n):
        if 3 <= sum(1 for l in max_child[i] + [max_parent[i]] if l >= body_len):
            can_turn[i] = True
            ok = True
    if not ok:
        print("NO")
        return
    treelen = [1] * body_len
    # print(body)
    for i in range(body_len):
        cur = body[i]
        pre = -1 if i == 0 else body[i - 1]
        nxt = -1 if i + 1 == body_len else body[i + 1]
        for v in adj[cur]:
            if v == pre or v == nxt:
                continue
            treelen[i] = max(treelen[i], max_child[v][0] + 1)
            if can_turn[v]:
                can_turn[cur] = True
                continue
            # dfs 3
            stack = [(v, cur)]
            while stack and not can_turn[cur]:
                u, p = stack.pop()
                for w in adj[u]:
                    if w == p:
                        continue
                    if can_turn[w]:
                        can_turn[cur] = True
                        break
                    stack.append((w, u))
            stack.clear()
            # end of dfs 3
        # print(i, cur, can_turn[cur])
    # use two pointer to find if we can enter the turing point
    # print(body_len, treelen)
    l = 0
    r = body_len - 1
    lmax = treelen[r] - 1
    rmin = body_len - treelen[l]
    ok = (can_turn[body[l]] or can_turn[body[r]])
    while not ok and (l < lmax or rmin < r):
        if l < lmax:
            l += 1
            rmin = min(rmin, l + (body_len - treelen[l]))
        if rmin < r:
            r -= 1
            lmax = max(lmax, r - (body_len - treelen[r]))
        if can_turn[body[l]] or can_turn[body[r]]:
            ok = True
    ##
    print("YES" if ok else "NO")
    return
    # end of solve


def __starting_point():
    # solve()
    # for t in range(getint()):
    #     print('Case #', t + 1, ': ', sep='')
    #     solve()
    for _ in range(getint()):
        solve()

__starting_point()

import sys
from collections import deque

t = int(input())
for _ in range(t):
    n, a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    edges = set()
    adj = [[] for x in range(n)]
    for _ in range(n-1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        u -= 1
        v -= 1
        edges.add((u, v))
        edges.add((v, u))
        adj[u].append(v)
        adj[v].append(u)


    to_a = [-1 for x in range(n)]
    to_a[a] = a
    stack = [a]
    while len(stack):
        cur = stack.pop()
        for nb in adj[cur]:
            if to_a[nb] == -1:
                to_a[nb] = cur
                stack.append(nb)

    snake = [b]
    while snake[-1] != a:
        snake.append(to_a[snake[-1]])

    snake = deque(snake)

    adj = [set(l) for l in adj]
    leaves = [x for x in range(n) if len(adj[x]) == 1]
    num_branch_points = sum([1 for l in adj if len(l) >= 3])
    new_leaves = []

    if len(snake) == 2:
        print("YES" if num_branch_points >= 1 else "NO")
        continue

    while True:
        head = snake.pop()
        tail = snake.popleft()
        if len(adj[head]) == 1 and len(adj[tail]) == 1:
            print("NO")
            break
        if len(adj[head]) != 1:
            snake.append(head)
        else:
            snake.appendleft(tail)

        for leaf in leaves:
            if len(adj[leaf]) == 0:
                continue
            nb = adj[leaf].pop()
            adj[nb].remove(leaf)
            if len(adj[nb]) == 2:
                num_branch_points -= 1
            if len(adj[nb]) == 1:
                new_leaves.append(nb)

        leaves, new_leaves = new_leaves, []
        
        if num_branch_points == 0:
            print("NO")
            break
        
        if len(snake) == 2:
            print("YES")
            break


import sys
from collections import deque

t = int(input())
for _ in range(t):
    n, a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    edges = set()
    adj = [[] for x in range(n)]
    for _ in range(n-1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        u -= 1
        v -= 1
        edges.add((u, v))
        edges.add((v, u))
        adj[u].append(v)
        adj[v].append(u)


    to_a = [-1 for x in range(n)]
    to_a[a] = a
    stack = [a]
    while len(stack):
        cur = stack.pop()
        for nb in adj[cur]:
            if to_a[nb] == -1:
                to_a[nb] = cur
                stack.append(nb)

    snake = [b]
    while snake[-1] != a:
        snake.append(to_a[snake[-1]])

    snake = deque(snake)

    adj = [set(l) for l in adj]
    leaves = [x for x in range(n) if len(adj[x]) == 1]
    num_branch_points = sum([1 for l in adj if len(l) >= 3])
    new_leaves = []

    if len(snake) == 2:
        print("YES" if num_branch_points >= 1 else "NO")
        continue

    while True:
        head = snake.pop()
        tail = snake.popleft()
        if len(adj[head]) == 1 and len(adj[tail]) == 1:
            print("NO")
            break
        if len(adj[head]) != 1:
            snake.append(head)
        else:
            snake.appendleft(tail)

        for leaf in leaves:
            if len(adj[leaf]) == 0:
                continue
            nb = adj[leaf].pop()
            adj[nb].remove(leaf)
            if len(adj[nb]) == 2:
                num_branch_points -= 1
            if len(adj[nb]) == 1:
                new_leaves.append(nb)

        leaves, new_leaves = new_leaves, []
        
        if num_branch_points == 0:
            print("NO")
            break
        
        if len(snake) == 2:
            print("YES")
            break

import sys
from collections import deque
 
t = int(input())
for _ in range(t):
    n, a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    edges = set()
    adj = [[] for x in range(n)]
    for _ in range(n-1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        u -= 1
        v -= 1
        edges.add((u, v))
        edges.add((v, u))
        adj[u].append(v)
        adj[v].append(u)
 
 
    to_a = [-1 for x in range(n)]
    to_a[a] = a
    stack = [a]
    while len(stack):
        cur = stack.pop()
        for nb in adj[cur]:
            if to_a[nb] == -1:
                to_a[nb] = cur
                stack.append(nb)
 
    snake = [b]
    while snake[-1] != a:
        snake.append(to_a[snake[-1]])
 
    snake = deque(snake)
 
    adj = [set(l) for l in adj]
    leaves = [x for x in range(n) if len(adj[x]) == 1]
    num_branch_points = sum([1 for l in adj if len(l) >= 3])
    new_leaves = []
 
    if len(snake) == 2:
        print("YES" if num_branch_points >= 1 else "NO")
        continue
 
    while True:
        head = snake.pop()
        tail = snake.popleft()
        if len(adj[head]) == 1 and len(adj[tail]) == 1:
            print("NO")
            break
        if len(adj[head]) != 1:
            snake.append(head)
        else:
            snake.appendleft(tail)
 
        for leaf in leaves:
            if len(adj[leaf]) == 0:
                continue
            nb = adj[leaf].pop()
            adj[nb].remove(leaf)
            if len(adj[nb]) == 2:
                num_branch_points -= 1
            if len(adj[nb]) == 1:
                new_leaves.append(nb)
 
        leaves, new_leaves = new_leaves, []
        
        if num_branch_points == 0:
            print("NO")
            break
        
        if len(snake) == 2:
            print("YES")
            break