Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has a non-direct graph with $n$ vertices and $n$ edges. Now he wants you to tell him if there exist a Hamiltonian path.

It is too difficult for Rikka. Can you help her?

Yuta has a non-direct graph with $n$ vertices and $n$ edges. Now he wants you to tell him if there exist a Hamiltonian path.

It is too difficult for Rikka. Can you help her?

There are no more than 100 testcases.

For each testcase, the first line contains a number $n(1 \leq n \leq 1000)$.

Then $n$ lines follow. Each line contains two numbers $u,v(1 \leq u,v \leq n)$ , which means there is an edge between $u$ and $v$.

For each testcase, the first line contains a number $n(1 \leq n \leq 1000)$.

Then $n$ lines follow. Each line contains two numbers $u,v(1 \leq u,v \leq n)$ , which means there is an edge between $u$ and $v$.

提交代码