정점이 $n$개인 무방향 트리가 주어진다. 리프는 차수가 $1$인 정점이다. 리프의 개수를 $k$라고 하자. 처음에는 각 리프에 토큰이 하나씩 있으므로, 토큰은 총 $k$개이다.

각 토큰에 대해, 모든 $i \ge 1$에 대해 $a_i \ne a_{i+1}$이고 $a_1 \ne v$인 무한한 리프 수열 $a_1, a_2, a_3, \ldots$을 선택해야 한다. 여기서 $v$는 그 토큰이 출발하는 리프이다. 서로 다른 토큰의 수열은 독립적으로 선택할 수 있다. 선택한 수열은 토큰의 경로를 결정한다. 토큰은 먼저 $v$에서 $a_1$까지의 최단 경로를 따라 이동하고, 그다음 $a_1$에서 $a_2$까지의 최단 경로를 따라 이동하고, 그다음 $a_2$에서 $a_3$까지 이동하는 식으로 무한히 이동한다.

한 번의 이동에서 모든 토큰은 동시에 각자의 경로에서 정확히 하나의 간선을 지난다. 어떤 토큰도 제자리에 머물 수 없다.

유한한 횟수의 이동 후에 모든 $k$개의 토큰이 동시에 같은 리프에 있도록 수열을 선택할 수 있는지 판별하라.

입력

첫 번째 줄에는 테스트 케이스의 개수인 정수 $t$ ($1 \le t \le 10^4$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 트리의 정점 개수인 정수 $n$ ($2 \le n \le 2 \cdot 10^5$)이 주어진다.

다음 $n-1$개의 줄에는 각각 두 정수 $u$와 $v$ ($1 \le u, v \le n$)가 주어지며, 이는 정점 $u$와 $v$ 사이의 양방향 간선을 나타낸다. 이 간선들이 트리를 이룸이 보장된다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \cdot 10^5$를 넘지 않음이 보장된다.

출력

각 테스트 케이스의 답을 별도의 줄에 출력하라. 모든 토큰에 대해 조건을 만족하는 수열을 선택하여 모든 토큰이 동시에 하나의 리프에 모이게 할 수 있다면 YES를 출력하고, 그렇지 않다면 NO를 출력하라.

예제

입력 1

5
2
1 2
3
2 1
2 3
4
1 2
1 3
3 4
6
1 2
2 3
2 4
4 5
4 6
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8

출력 1

NO
NO
NO
NO
YES