While studying the graph isomorphism problem, Pog encountered some difficulties. As is well known, graph isomorphism is a famous problem in computational complexity theory, and its exact complexity remains undetermined to this day. Therefore, Pog decided to modify the definition of the graph isomorphism problem.

First, in a weighted undirected graph $G$, the weight of a path $u \to x_1 \to \dots \to x_k \to v$ is defined as the maximum weight of all edges on this path.

Next, the distance $\text{dis}_{G,u,v}$ between two distinct vertices $u, v$ ($u \neq v$) in graph $G$ is defined as the minimum weight among all paths from $u$ to $v$. If $u$ and $v$ are not connected (i.e., there is no path from $u$ to $v$), then $\text{dis}_{G,u,v} = +\infty$.

Two graphs $G_1$ and $G_2$ with $n$ vertices, labeled $1, 2, \dots, n$, are defined to be isomorphic if and only if for all $u, v$ ($1 \le u, v \le n, u \neq v$), $\text{dis}_{G_1,u,v} = \text{dis}_{G_2,u,v}$. Please note that this definition is different from the standard notion of isomorphism; re-labeling is not allowed.

Now, please help Pog determine whether two given graphs are isomorphic under this new definition.

Input

The input contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case: The first line contains three integers $n, m_1, m_2$ ($1 \le n \le 10^5, 1 \le m_1, m_2 \le 2 \times 10^5$), representing the number of vertices and the number of edges in $G_1$ and $G_2$, respectively. The next $m_1$ lines each contain three integers $u, v, w$ ($1 \le u, v \le n, 1 \le w \le 10^9$), representing an edge in $G_1$. The next $m_2$ lines each contain three integers $u, v, w$ ($1 \le u, v \le n, 1 \le w \le 10^9$), representing an edge in $G_2$.

It is guaranteed that the sum of $n$ over $T$ test cases does not exceed $10^5$, and the sum of $m_1$ and the sum of $m_2$ do not exceed $2 \times 10^5$. Note that the graphs may contain multiple edges, self-loops, and may not be connected.

Output

For each test case: Output a single line containing a string: if they are isomorphic, output YES, otherwise output NO (case-insensitive).

Examples

Input 1

3
2 1 1
1 2 1
1 2 2
2 1 1
1 2 1
1 2 1
3 3 3
1 2 1
1 3 1
2 3 2
1 2 1
1 3 2
2 3 1

Output 1

NO
YES
YES