Trên đường đi tìm cha, cậu bé Gon lạc đến đảo Tham Lam. Hòn đảo này rất kỳ quái, người dân không dùng tiền mà dùng thẻ để trao đổi. Trên mỗi thẻ ghi một số nguyên nằm trong đoạn \([1, N]\) và được gọi là mã số của thẻ. Chỉ có một cách duy nhất để ra khỏi đảo là đem được \(N\) thẻ có mã đôi một khác nhau (tức là mã \(1, 2, \ldots, N\)) đổi lấy vé tàu.

Gon có 2 cách để kiếm thẻ ở trên đảo:

• Nhặt thẻ mà người khác đánh rơi
• Trao đổi với ngân hàng của đảo: dùng 1 thẻ của mình đổi lấy 1 thẻ khác của ngân hàng, lệ phí 1 lần đổi là 1 cục vàng (ngân hàng dùng để đúc thẻ mới)

Rất may là Gon được một người bạn tốt bụng tặng cho \(N\) thẻ nên chỉ còn phải ra ngân hàng đổi thẻ (để được \(N\) thẻ khác nhau đôi một). Vì chuyến đi dài nên Gon phải tiết kiệm vàng. Bạn hãy giúp Gon tìm cách đổi để tốn ít vàng nhất mà vẫn đổi được vé tàu đi ra khỏi đảo. Biết rằng luôn tồn tại ít nhất một cách đổi.

Input

• Dòng thứ nhất ghi số nguyên \(N\) \((N \leq 100)\)
• Dòng thứ hai ghi \(N\) số nguyên là mã số của \(N\) thẻ mà Gon có
• Tiếp theo là một số dòng, trên mỗi dòng chứa hai số \(u, v\) có nghĩa là có thể đổi thẻ có mã số \(u\) của Gon lấy thẻ có mã số \(v\) của ngân hàng và ngược lại.

Các dữ liệu số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là tổng số vàng ít nhất phải trả khi đổi thẻ.

Example

4
1 1 1 1
1 2
2 3
1 4
3 4

4