Submit solution
Points:
0.74 (partial)
Time limit:
3.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho một cây (đồ thị vô hướng phi chu trình) có ~N~ nút. Các nút của cây được đánh số từ 1 đến ~N~. Ban đầu, mỗi nút đều có màu trắng.
Bạn phải thực hiện các thao tác có dạng sau:
- ~0 \, i~: đổi màu nút thứ ~i~ (từ đen thành trắng, hoặc từ trắng thành đen)
- ~1 \, v~: tìm chỉ số của nút đen đầu tiên trên đường đi từ nút 1 đến nút ~v~. Nếu không tồn tại, hãy trả về -1.
Input
- Dòng thứ nhất gồm hai số nguyên ~N~ và ~Q~. ~(1 \le N, Q \le 10^5)~.
- ~N-1~ dòng sau, mỗi dòng gồm hai số nguyên ~a~, ~b~ mô tả một cạnh nối giữa nút ~a~ và nút ~b~ ~(1 \le a, b \le N)~.
- ~Q~ dòng sau chứa các thao tác dạng ~0 \, i~ hoặc ~1 \, v~ ~(1 \le i, v \le N)~.
Output
Với mỗi thao tác dạng ~1 \, v~, in ra một số nguyên là kết quả.
Sample Input
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9
Sample Output
-1
8
-1
2
-1
Comments