Archive Tree#13102

Archive Tree

1 second
256 megabytes

An archive consists of folders numbered from to . Some pairs of folders are directly linked, there are n - 1 such links in total, and from any folder one can reach any other one through the links; in other words, the folders and the links form a tree. Folder is the root folder.

For every folder v \ne s, its parent folder is the neighbour of on the path from to the root folder, and is called a subfolder of its parent.

Every folder must be given a name f_v, which is a positive integer. By the convention of the archive, the names must satisfy the following rules:

Short names are easier to type, so the administrator wants the largest name in the archive to be as small as possible. Find the minimum possible value of \max\limits_{1 \le v \le n} f_v.

Input

The first line contains a single integer (1 \le t \le 5 \cdot 10^5) — the number of test cases.

The first line of each test case contains two integers and (1 \le s \le n \le 5 \cdot 10^5) — the number of folders and the number of the root folder. Each of the next n - 1 lines contains two integers and (1 \le u, v \le n, u \ne v) — the folders connected by a link. It is guaranteed that the links form a tree.

The sum of over all test cases does not exceed 5 \cdot 10^5.

Output

For each test case print one integer — the minimum possible largest name.

Examples

Example 1

Loading
Loading

Note

In the first test case the root folder is , and it has the subfolders , and . Folder has the subfolders and , and folder has the subfolders and . One optimal assignment of names is:

  • f_4 = 1;

  • f_1 = 1, f_2 = 2, f_8 = 3;

  • f_3 = 1, f_5 = 2;

  • f_6 = 2, f_7 = 4.

It can be shown that the largest name cannot be less than .

In the second test case the folders form the chain 1 - 2 - 3 - 4 - 5 with the root folder in the middle. Folders and are subfolders of the root folder, so they need different names. For example, f_1 = f_2 = f_3 = 1 and f_4 = f_5 = 2, so the answer is .

In the third test case there is only the root folder, and f_1 = 1.