logo AlgoBeat OnlineJudge
登录 注册

#216131. [USTCPC 2026] Doughnut

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

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

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


甜甜圈星人居住在一个甜甜圈形状的星球上,为了方便管理,甜甜圈国王在星球上画了 个纬圆(如图中点线)和 个经圆(如图中虚线),将地表划分为 个区域,并编号为

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

甜甜圈星球示意图

输入格式

本题有多组测试数据。

首先输入一行,包含一个整数 (),表示测试数据组数。

每组数据首先输入一行,包含一个整数 (),表示区域邻接关系的总数。

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

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

保证

输出格式

输出 行,每行一个整数,表示 的值。若无法唯一确定 的值,输出

样例

样例输入 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

数据范围与提示

第一组样例中, 中一个为 ,另一个为 ,可证明不存在其他可能性。

第二组样例中, 中一个为 ,另一个为 ,可证明不存在其他可能性。