Bạn đã đi bộ trong rừng hàng giờ và muốn về nhà.

Khu rừng có \(N\) khoảng trống được đánh số \(1, 2, \dots, N\). Hiện tại bạn đang ở khoảng trống 1, và bạn phải đến được khoảng trống \(N\) để rời khỏi khu rừng. Mỗi khoảng trống từ 1 đến \(N-1\) có một lối đi bên trái và một lối đi bên phải dẫn đến các khoảng trống khác, cũng như một số lối đi một chiều dẫn vào. Thật không may, khu rừng bị ám, và bất cứ khi nào bạn đi vào một khoảng trống, một trong hai lối đi ra sẽ bị chặn bởi những cái cây dịch chuyển. Chính xác hơn, trong lần ghé thăm thứ \(k\) của bạn tới bất kỳ một khoảng trống nào:

• Bạn phải rời đi theo lối đi bên trái nếu \(k\) là số lẻ.
• Bạn phải rời đi theo lối đi bên phải nếu \(k\) là số chẵn.
• Tất cả các lối đi đều là một chiều, vì vậy bạn không có lựa chọn nào ở mỗi bước: bạn phải đi tiếp qua lối đi duy nhất không bị chặn.

Vì vậy, lần đầu tiên bạn ở khoảng trống số 1, bạn sẽ rời đi theo lối đi bên trái. Nếu bạn quay lại khoảng trống số 1 lần thứ hai, bạn sẽ rời đi theo lối đi bên phải; lần thứ ba, bạn lại rời đi theo lối đi bên trái; và cứ thế tiếp tục.

Bạn bắt đầu tại khoảng trống số 1, và khi bạn đến khoảng trống số \(N\), bạn có thể rời khỏi khu rừng. Bạn cần đi qua bao nhiêu lối đi trước khi thoát ra ngoài?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\).

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\). Ở đây, \(L_i\) đại diện cho khoảng trống bạn sẽ đến nếu đi theo lối đi bên trái từ khoảng trống \(i\), và \(R_i\) đại diện cho khoảng trống bạn sẽ đến nếu đi theo lối đi bên phải từ khoảng trống \(i\).

Không có lối đi nào được chỉ định cho khoảng trống \(N\) vì khi bạn đến đó, bạn đã hoàn thành.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng lối đi bạn cần thực hiện để đến được khoảng trống \(N\). Nếu bạn không bao giờ đến được khoảng trống \(N\), hãy xuất "Infinity" thay thế.

Ràng buộc

• \(1 \le T \le 30\).
• \(1 \le L_i, R_i \le N\) với mọi \(i\).

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(2 \le N \le 10\).
• Tập kiểm tra 2 (Hidden Verdict): \(2 \le N \le 40\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Case #1: 8
Case #2: Infinity

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Shifting Paths.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.