Trốn tìm

An và Bình đang chơi một trò chơi trốn tìm trong ngôi nhà của họ. Ngôi nhà có \(n\) phòng
và \(m\) cặp phòng được nối với nhau bằng cửa. Các phòng được đánh số từ \(1\) đến \(n\),
và giữa bất kỳ hai phòng nào cũng tồn tại một đường đi.

Bình có một chiến thuật trốn như sau: mỗi khi An bước vào phòng \(v\), Bình sẽ trốn trong phòng \(a_v\).
Ở thời điểm bắt đầu, An chọn phòng xuất phát \(v_0\), và Bình sẽ trốn trong phòng \(a_{v_0}\).

Mỗi lượt chơi diễn ra theo thứ tự:
(1) An chọn một phòng kề với phòng hiện tại của mình và di chuyển sang đó.
(2) Ngay lập tức, Bình biết An đang ở đâu và lập tức di chuyển (có thể đi qua nhiều phòng trong một lượt) tới phòng \(a_u\) tương ứng với phòng mới của An.

Trò chơi kết thúc ngay khi cả hai ở trong cùng một phòng.

Với mỗi phòng xuất phát của An, hãy xác định xem An có thể tìm được Bình trong số bước hữu hạn hay không.
Nếu có, hãy tính số bước ít nhất An cần để chắc chắn tìm thấy Bình, giả sử cả hai đều chơi tối ưu:
An muốn kết thúc trò chơi càng sớm càng tốt, còn Bình muốn kéo dài thời gian càng lâu càng tốt.

\InputFile

Dòng đầu gồm hai số nguyên \(n, m\)
(\(1 \le n \le 2 \cdot 10^5\), \(n - 1 \le m \le \min(5 \cdot 10^5, \frac{n(n-1)}{2})\)) ---
số phòng và số cặp phòng có cửa nối.

Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(1 \le a_i \le n\)), mô tả chiến thuật trốn của Bình.

Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số \(x_i, y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)),
cho biết phòng \(x_i\) và phòng \(y_i\) có cửa nối trực tiếp. Giữa hai phòng bất kỳ có nhiều nhất một cửa.

\OutputFile

In ra \(n\) số.
Số thứ \(i\) là số bước ít nhất để An có thể tìm thấy Bình nếu bắt đầu từ phòng \(i\),
hoặc \(-1\) nếu An không thể tìm thấy Bình.

\Scoring

\begincenter
\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 15 &
\(\, n \le 1000,\; m \le 2000\)

2 & 25 &
\(m = n - 1\)

3 & 30 &
Bình sẽ không bao giờ trốn trong phòng liền kề hoặc trùng với phòng An đang đứng,
và cấu trúc ngôi nhà đảm bảo trò chơi kết thúc trong không quá \(5\) phòng khác nhau

4 & 30 &
Không có ràng buộc bổ sung.

\hline
\endtabular
\endcenter

\Examples

\beginexample
\exmp
4 4
3 4 1 2
1 2
2 3
3 4
4 1

-1 -1 -1 -1

\exmp
8 9
2 3 2 1 6 5 6 7
1 2
1 3
2 4
3 4
4 5
4 6
6 7
5 7
4 8

1 2 2 2 1 1 1 1

\exmp
9 8
1 9 1 1 1 9 9 9 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

0 1 1 2 1 1 2 1 1

\endexample

\Note

Trong ví dụ thứ hai:
An di chuyển từ phòng \(4\) sang phòng \(8\) ở lượt đầu tiên, và ở lượt thứ hai quay trở lại phòng \(4\).
Bình buộc phải đi qua phòng \(4\) để có thể đi từ phòng \(7\) về phòng \(1\),
vì vậy An tìm được Bình sau \(2\) bước.

\endproblem