Background

Today is another peaceful day. Kruskal-chan is in the library, struggling with graph theory.

Suddenly, a book called A Guide to Doughnut Planet fell off the shelf, with a note inside:

"Dear Kruskal-chan, we sincerely invite you to Doughnut Planet to help us compute $n+m$! You remember all region adjacency relations, right?"

Huh? What is going on? Could it be that my graph theory skills have already spread across the universe?

Problem Description

The Doughnut people live on a doughnut-shaped planet. For easier management, the Doughnut King drew $n$ latitude circles (dotted lines in the figure) and $m$ longitude circles (dashed lines in the figure) on the planet, dividing the surface into $nm$ regions, numbered from $1$ to $nm$.

Kruskal is invited to visit Doughnut Planet. Since she has just learned graph theory, she remembers all region adjacency relations (i.e., which regions are adjacent). Can you help her compute the value of $n+m$?

Input Format

This problem contains multiple test cases.

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

For each test case, the first line contains an integer $k$ ($0\le k\le 10^5$), the total number of region adjacency relations.

Then follow $k$ lines, each containing two integers $u,v$, indicating that region $u$ is adjacent to region $v$.

Note: The adjacency relations are guaranteed to be generated by some pair $n,m$, but they may be given in any order.

It is guaranteed that $\sum k\le 10^5$.

Output Format

Output $T$ lines. Each line contains one integer, the value of $n+m$. If $n+m$ cannot be uniquely determined, output $-1$.

2
1
1 2
9
1 2
2 3
3 1
4 5
5 6
6 4
1 6
2 5
3 4

3
5

Hint

In the first sample, one of $n,m$ is $1$ and the other is $2$. It can be proven that no other possibility exists.

In the second sample, one of $n,m$ is $2$ and the other is $3$. It can be proven that no other possibility exists.

Translated by ChatGPT 5