Green Hackenbush Trên Cây
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Cho k cây (rừng), mỗi cây bám rễ tại một đỉnh gốc trên mặt đất. Cây thứ i có n_i đỉnh và n_i - 1 cạnh.
Hai người chơi thay phiên nhau chơi trò chơi Green Hackenbush. Mỗi lượt, người chơi chọn một cạnh bất kỳ trong rừng và xóa nó. Khi một cạnh bị xóa, tất cả các phần không còn kết nối với mặt đất (gốc) sẽ bị loại bỏ. Người chơi nào không thể thực hiện nước đi (không còn cạnh nào) sẽ thua.
Người chơi đầu tiên đi trước. Xác định ai sẽ thắng nếu cả hai chơi tối ưu.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên k (1 ≤ k ≤ 10^5) — số cây.
- Tiếp theo là mô tả k cây:
- Dòng đầu của mỗi cây chứa n_i (1 ≤ n_i ≤ 10^5) — số đỉnh. Đỉnh 1 là gốc.
- n_i - 1 dòng tiếp theo, mỗi dòng chứa hai số u, v — cạnh nối u và v.
- Tổng n_i qua tất cả cây không vượt quá 2 × 10^5.
Dữ liệu ra
- In ra "First" nếu người chơi đầu tiên thắng, "Second" nếu người chơi thứ hai thắng.
Ví dụ
Input
2
3
1 2
2 3
4
1 2
1 3
3 4
Output
First
Giải thích
- Cây 1: gốc 1, cạnh 1-2, 2-3. Giá trị Grundy = nim-value của cây = XOR các nhánh.
- Đỉnh 3: lá, Grundy từ cạnh 2-3 = 1.
- Đỉnh 2: có 1 con (3) với giá trị 1, nên Grundy cạnh 1-2 = 1+1 = 2.
- Grundy cây 1 = 2.
- Cây 2: gốc 1, con 2 (lá, giá trị 1) và 3 (có con 4 lá, giá trị 1+1=2). Grundy = 1 XOR 2 = 3.
- Tổng XOR = 2 XOR 3 = 1 ≠ 0 → First thắng.
Giới hạn
- 1 ≤ k ≤ 10^5
- 1 ≤ n_i ≤ 10^5
- Tổng n_i ≤ 2 × 10^5
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion