Tổ Tiên Chung Gần Nhất

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami có một cái cây gốc ở 1 và \(q\) truy vấn có dạng \(u\) \(v\). Hãy tìm tổ tiên chung gần nhất của \(u\)\(v\).

Input

  • Dòng đầu tiên chứa \(t\) là số câu hỏi.

Mỗi câu hỏi có dạng sau:

  • Dòng đầu tiên chứa \(1\) số nguyên \(N\) là số đỉnh của cây.

  • \(N\) dòng tiếp theo, mỗi dòng \(i\) bắt đầu bằng \(1\) số nguyên \(k\), theo sau đó là \(k\) số \(a_1, a_2,...., a_k\) là các nút con của đỉnh \(i\).

  • Sau đó là một số nguyên dương \(q\) - số lượng truy vấn.
    \(Q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(u\)\(v\) là một câu hỏi.

Output

  • \(Q\) dòng, mỗi dòng là tổ tiên chung gần nhất tương ứng.

Constraints

  • \(1 \leq u , v \leq N\)
  • \(1 \leq N \leq 1000\).
  • \(1 \leq Q \leq 3000\).

Example

Test 1

Input
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7 
Output
Case 1:
3
1
Note


Bình luận

Không có bình luận nào.