题目描述

You have been walking in the woods for hours, and you want to go home.

The woods contain $N$ clearings labeled $1, 2, \dots, N$. You are now at clearing $1$, and you must reach clearing $N$ in order to leave the woods. Each clearing from $1$ to $N-1$ has a left path and a right path leading out to other clearings, as well as some number of one-way paths leading in. Unfortunately, the woods are haunted, and any time you enter a clearing, one of the two outgoing paths will be blocked by shifty trees. More precisely, on your $k^{th}$ visit to any single clearing:

• You must leave along the left path if $k$ is odd.
• You must leave along the right path if $k$ is even.
• All paths are one-way, so you have no choice at each step: you must go forward through the one unblocked outgoing path.

So the first time you are in clearing #1, you will leave along the left path. If you ever come back to clearing #1 for a second time, you would leave along the right path; the third time, you'd leave along the left path again; and so on.

You begin at clearing #1, and when you get to clearing #N, you can leave the woods. How many paths do you need to follow before you get out?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, each beginning with a line containing a single integer $N$.

$N-1$ lines follow, each containing two integers $L_i$ and $R_i$. Here, $L_i$ represents the clearing you would end up at if you follow the left path out of clearing $i$, and $R_i$ represents the clearing you would end up at if you follow the right path out of clearing $i$.

No paths are specified for clearing $N$ because once you get there, you are finished.

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the case number (starting from 1) and $y$ is the number of paths you need to follow to get to clearing $N$. If you will never get to clearing $N$, output "Infinity" instead.

2
4
2 1
3 1
2 4
3
2 2
1 2

Case #1: 8
Case #2: Infinity

提示

Sample Explanation

In the first sample case, your route through the woods will be as shown below:

Paths followed	Clearing	Path direction
0	1	Left
1	2
2	3
3	2	Right
4	1
5		Left
6	2
7	3	Right
8	4	-

Limits

• $1 \leq T \leq 30.$
• $1 \leq L_i, R_i \leq N$ for all $i$.

Test set 1 (5 Pts, Visible Verdict)

• $2 \leq N \leq 10.$

Test set 2 (46 Pts, Hidden Verdict)

• $2 \leq N \leq 40.$