该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

做题前请先阅读如下内容

附加题特别告知

本题为附加题，请视情况选做。

分卷题特别告知

由于技术原因，本题为分卷题，分A,B两卷，本卷是A卷，请使用相同代码提交两卷，两卷得分之和为您本题得分，若您没有使用相同代码提交两卷或只提交了其中一卷，您的本题成绩可能会被取消。

---

题面

小宋准备回家了，他在点\(1\)，无奈他是个路痴，给出城市格局，问他是否会中途走回去，即图上是否有环。
这个城市非常特殊，每个路口的来源路口只有一个。

输入格式

第一行一个数\(T\)，数据组数
每组数据第一行一个数\(n\)表示节点数，接下来\(n\)行每行两个数\(u,v\)表示能从\(u\)走到\(v\)。
无重边、反向边重边及自环的情况，保证图是一张连通图，每个相邻整数间以空格分割

输出格式

每组数据输出一行，0（不会）或1（会）

输入样例

1
3
1 2
2 3
3 1

输出样例

1

数据范围

对于10%的数据，\(1 \le u,v \le 1000\),\(t=1\)，时间限制1s，分数1分一个点
对于另外20%的数据，\(1 \le u,v \le 10000\),\(t \le 10\)，时间限制1s，分数4分一个点
对于其余70%的数据，\(1 \le u,v \le n \le 100000\),\(1 \le t \le 100\)，时间限制0.01s，分数13分一个点