This is the hard version of the problem. The difference between the versions is that in this version, $t \le 10^4$, $n \le 2 \cdot 10^5$ and the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. You can hack only if you solved all versions of this problem.

The rivals Axial and Nife have had yet another argument, and they decided to settle it by playing a game on a tree.

They are given a tree with $n$ vertices numbered from $1$ to $n$. Each vertex contains either $0$ or $1$. Initially, two distinct vertices $x$ and $y$ contain $0$, and all other vertices contain $1$.

The players take turns, with Axial going first. On each turn, the current player chooses a vertex $v$ containing $1$ and changes its value to $0$. Before changing the value of $v$, let $c_v$ be the number of neighbors of $v$ that contain $0$. If $c_v = 1$, the current player gets one point. Otherwise, they get no points. The game ends when all vertices contain $0$.

Let $p$ and $q$ be the final scores of Axial and Nife, respectively. Axial wants to maximize $p - q$, while Nife wants to minimize it. Assuming both players play optimally, determine the value of $p - q$ at the end of the game.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $x$, and $y$ ($2 \le n \le 2 \cdot 10^5$, $1 \le x, y \le n$, $x \ne y$) — the number of vertices in the tree and the two vertices that initially contain $0$.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$), denoting an edge between vertices $u$ and $v$.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the value of $p - q$ at the end of the game.

Note

In the figures below, blue vertices initially contain $0$, while white vertices initially contain $1$.

For the first example, the initial state is:

Axial changes vertex $3$ to $0$. It has exactly one neighbor containing $0$, so Axial gets one point. Therefore, $p - q=1$.

For the second example, the initial state is:

Axial can change either vertex $2$ or vertex $3$ to $0$ and get one point. After that, the remaining vertex has two neighbors containing $0$, so Nife gets no points. Therefore, $p - q=1$.

For the third example, the initial state is:

The only possible move is to change vertex $2$ to $0$. It has two neighbors containing $0$, so Axial gets no points. Therefore, $p - q=0$.