Arezou và em trai Borzou là hai chị em sinh đôi. Nhân dịp sinh nhật, họ được tặng một bộ đồ chơi tàu hỏa và dùng nó để xây dựng một hệ thống gồm \(n\) ga tàu cùng \(m\) đường ray một chiều. Các ga được đánh số từ \(0\) đến \(n-1\). Mỗi đường ray xuất phát từ một ga và kết thúc tại chính ga đó hoặc một ga khác. Từ mỗi ga có ít nhất một đường ray đi ra.

Một số ga là ga nạp pin. Khi tàu đến một ga nạp pin, pin của tàu được nạp đầy. Một lần nạp đầy cung cấp đủ năng lượng để tàu đi hết \(n\) đường ray liên tiếp. Nếu không được nạp lại, tàu sẽ hết năng lượng khi vừa bắt đầu đi vào đường ray thứ \(n+1\) kể từ lần nạp gần nhất.

Tại mỗi ga có một nút điều khiển có thể trỏ đến bất kỳ đường ray nào xuất phát từ ga đó. Khi rời một ga, tàu đi theo đường ray mà nút điều khiển tại ga ấy đang trỏ đến.

Hai chị em chơi một trò chơi với chiếc tàu này. Họ chia tất cả các ga cho nhau: mỗi ga thuộc sở hữu của Arezou hoặc Borzou. Chỉ có một chiếc tàu. Khi trò chơi bắt đầu, tàu ở ga \(s\) với pin đã được nạp đầy. Người sở hữu ga \(s\) thiết lập nút điều khiển tại đó, chọn một đường ray đi ra, rồi cho tàu chạy.

Mỗi khi tàu đến một ga lần đầu tiên, người sở hữu ga ấy thiết lập nút điều khiển tại ga. Sau khi được thiết lập, nút điều khiển không được thay đổi trong suốt trò chơi. Vì vậy, khi quay lại một ga đã ghé qua, tàu luôn rời ga bằng đúng đường ray đã chọn trước đó.

Do số ga hữu hạn, cuối cùng hành trình của tàu sẽ lặp lại theo một chu trình. Một chu trình gồm các ga đôi một khác nhau

trong đó tàu đi từ \(c[i]\) đến \(c[i+1]\) với mọi \(0\le i<k-1\), rồi từ \(c[k-1]\) về \(c[0]\). Chu trình có thể chỉ gồm một ga, tức là \(k=1\), nếu đường ray được chọn đi từ \(c[0]\) trở lại chính ga đó.

Arezou thắng nếu tàu có thể chạy mãi mãi; Borzou thắng nếu tàu hết pin. Nói cách khác, nếu chu trình có ít nhất một ga nạp pin thì tàu có thể liên tục nạp pin và chạy vô hạn, nên Arezou thắng. Nếu chu trình không có ga nạp pin, tàu sẽ hết pin, có thể sau khi đi quanh chu trình vài vòng, và Borzou thắng.

Cho mô tả hệ thống đường tàu. Hai chị em sẽ chơi \(n\) trò chơi độc lập; ở trò chơi thứ \(s\), với \(0\le s\le n-1\), tàu bắt đầu tại ga \(s\). Với mỗi trò chơi, hãy xác định liệu Arezou có chiến thuật bảo đảm chiến thắng, bất kể Borzou chơi như thế nào hay không.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp train.h:

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v);

• a: mảng độ dài \(n\). Với mỗi \(0\le i\le n-1\), \(a[i]=1\) nếu Arezou sở hữu ga \(i\); \(a[i]=0\) nếu Borzou sở hữu ga đó.
• r: mảng độ dài \(n\). Với mỗi \(0\le i\le n-1\), \(r[i]=1\) nếu ga \(i\) là ga nạp pin; ngược lại, \(r[i]=0\).
• u, v: hai mảng độ dài \(m\). Với mỗi \(0\le i\le m-1\), có một đường ray một chiều từ ga \(u[i]\) đến ga \(v[i]\).

Hàm phải trả về một mảng \(w\) có đúng \(n\) phần tử. Với mỗi \(0\le i\le n-1\), \(w[i]=1\) nếu Arezou có thể bảo đảm chiến thắng khi tàu bắt đầu ở ga \(i\), bất kể cách chơi của Borzou; ngược lại, \(w[i]=0\).

Chương trình chấm sẽ gọi hàm này và nhận kết quả trả về. Bạn không cần cài đặt hàm main.

Ví dụ

Xét lời gọi:

who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1});

Có hai ga tàu. Borzou sở hữu ga \(0\), là ga nạp pin. Arezou sở hữu ga \(1\), không phải ga nạp pin. Bốn đường ray là \((0,0)\), \((0,1)\), \((1,0)\) và \((1,1)\), trong đó \((i,j)\) biểu diễn đường ray một chiều từ ga \(i\) đến ga \(j\).

Nếu tàu bắt đầu tại ga \(0\) và Borzou chọn đường ray \((0,0)\), tàu sẽ chạy mãi trên đường ray này vì ga \(0\) có thể nạp pin, nên Arezou thắng. Nếu Borzou chọn \((0,1)\), Arezou có thể chọn \((1,0)\) tại ga \(1\). Khi đó, tàu chạy vô hạn theo chu trình qua hai ga và được nạp pin mỗi khi về ga \(0\). Vì thế, Arezou luôn có thể thắng khi tàu bắt đầu tại ga \(0\).

Tương tự, khi tàu bắt đầu tại ga \(1\), Arezou chọn \((1,0)\) và vẫn bảo đảm chiến thắng. Do đó, hàm phải trả về \([1,1]\).

Ràng buộc

• \(1\le n\le 5000\).
• \(n\le m\le 20\,000\).
• \(a[i],r[i]\in\{0,1\}\) với mọi \(0\le i\le n-1\).
• Có ít nhất một ga nạp pin.
• Từ mỗi ga có ít nhất một đường ray đi ra.
• Đường ray có thể xuất phát và kết thúc tại cùng một ga, tức là \(u[i]=v[i]\).
• Các đường ray đôi một khác nhau: không tồn tại hai chỉ số \(0\le i<j\le m-1\) sao cho đồng thời \(u[i]=u[j]\) và \(v[i]=v[j]\).
• \(0\le u[i],v[i]\le n-1\) với mọi \(0\le i\le m-1\).

Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

Chương trình chấm mẫu

Chương trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(a[0]\ a[1]\ \ldots\ a[n-1]\).
• Dòng \(3\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(4+i\), với \(0\le i\le m-1\): \(u[i]\ v[i]\).

Chương trình chấm mẫu in mảng do who_wins trả về trên một dòng, theo thứ tự \(w[0]\ w[1]\ \ldots\ w[n-1]\), các phần tử cách nhau bằng dấu cách.

Dữ liệu vào mẫu

2 4
0 1
1 0
0 0
0 1
1 0
1 1

Kết quả ra mẫu

1 1