You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

今天也是和平的一天～克露丝卡尔酱正在图书馆里与图论搏斗中。

突然，一本《甜甜圈星球导览》从书架上掉了下来，里面夹着一张纸条：

『亲爱的克露丝卡尔酱，我们诚挚邀请你来到甜甜圈星球，帮助我们计算 $n+m$！你记住了所有区域邻接关系对吧？』

咦？这、这是怎么回事？难道我的图论能力已经传遍宇宙了吗？

题目描述

甜甜圈星人居住在一个甜甜圈形状的星球上，为了方便管理，甜甜圈国王在星球上画了 $n$ 个纬圆（如图中点线）和 $m$ 个经圆（如图中虚线），将地表划分为 $nm$ 个区域，并编号为 $1\sim nm$。

克露丝卡尔被邀请去甜甜圈星球参观，由于她刚刚学习了图论，因此她记住了 所有的 区域邻接关系（即哪些区域之间是相邻的）。你能帮助她计算 $n+m$ 的值吗？

输入格式

本题有多组测试数据。

首先输入一行，包含一个整数 $T$ ($1\le T\le 10^5$)，表示测试数据组数。

每组数据首先输入一行，包含一个整数 $k$ ($0\le k\le 10^5$)，表示区域邻接关系的总数。

之后输入 $k$ 行，每行包含两个整数 $u,v$，表示编号为 $u$ 的区域与编号为 $v$ 的区域相邻。

注意：邻接关系一定由某组 $n,m$ 生成，但可能以任意顺序给出。

保证 $\sum k\le 10^5$。

输出格式

输出 $T$ 行，每行一个整数，表示 $n+m$ 的值。若无法唯一确定 $n+m$ 的值，输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

3
5

提示

第一组样例中，$n$、$m$ 中一个为 $1$，另一个为 $2$，可证明不存在其他可能性。

第二组样例中，$n$、$m$ 中一个为 $2$，另一个为 $3$，可证明不存在其他可能性。