Subtask 1: Ta đơn giản thực hiện các thao tác và xác định màu sắc cuối cùng cho mỗi đỉnh.

Độ phức tạp: ~O(Q(N+M))~

Subtask 2: Gọi ~color_{0,u}~ là màu sắc cuối cùng của thao tác với ~d=0~ hoặc ~d=1~ tại đỉnh ~u~ và ~color_{1,u}~ là màu sắc cuối cùng của thao tác với ~d=1~ tại đỉnh ~u~. Ta dễ dàng xây dựng mảng ~color~ bằng cách duyệt qua tất cả các thao tác.

Với mỗi đỉnh ~i~ cần xác định màu sắc cuối cùng được tô, ta cần tìm màu sắc xuất hiện sau cùng của một trong hai trường hợp:

• Có thao tác tô trực tiếp tại đỉnh ~i~ với ~d=0~ hoặc ~d=1~, dựa trên ~color_{0,i}~.
• Có thao tác tô tại đỉnh ~j~ là đỉnh liền kề với đỉnh ~i~, dựa trên ~color_{1,j}~

Độ phức tạp: ~O(N+M+Q)~

Subtask 3: Ta có thể thực hiện đảo ngược các thao tác, từ thao tác thứ ~Q~ đến thao tác thứ nhất. Khi đó, mỗi đỉnh được tô màu đầu tiên sẽ không thay đổi màu sắc ở những lần tô tiếp theo. Hay nói cách khác, đáp án màu sắc cho mỗi đỉnh là màu được tô đầu tiên của đỉnh đó.

Ta có thể giải quyết bằng phương pháp đệ quy. Gọi hàm ~Recursion(v,d,c)~ với mỗi thao tác:

• Nếu trạng thái hàm ~Recursion(v,d,c)~ đã được gọi trước đó thì ta không cần thực hiện hàm này.
• Nếu ~d=0~ thì gán kết quả màu sắc của đỉnh ~v~ bằng ~c~ và kết thúc hàm.
• Gọi hàm ~Recursion(v,d-1,c)~.
• Với mỗi đỉnh ~u~ liền kề với đỉnh ~v~, gọi hàm ~Recursion(u, d-1, c)~.

Từ đó, mỗi hàm ~Recursion(v,d,c)~ chỉ thực hiện một lần với việc lưu lại các trạng thái của hàm này.

Độ phức tạp: ~O(M+Q+N.\max\{d\})~