P16116 [USTCPC 2026] Doughnut

今天也是和平的一天～克露丝卡尔酱正在图书馆里与图论搏斗中。 突然，一本《甜甜圈星球导览》从书架上掉了下来，里面夹着一张纸条： 『亲爱的克露丝卡尔酱，我们诚挚邀请你来到甜甜圈星球，帮助我们计算 $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$。

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