Bạn chuẩn bị tổ chức một bữa tiệc tại nhà với ~N~ món đồ ăn có trong bữa tiệc. Mỗi loại đồ ăn sẽ có 1 món, tức là đồ ăn có trong bữa tiệc sẽ có các loại từ 1 đến ~N~.

Dự tính sẽ có ~K~ vị khách sẽ tới bữa tiệc của bạn. Mỗi vị khách sẽ có 2 loại đồ ăn ưa thích của họ.

Khi các vị khách đến với bữa tiệc, việc ăn đồ ăn của khách sẽ được diễn ra như sau:

• Bạn sẽ sắp xếp các vị khách theo thứ tự từ 1 đến ~K~
• Các vị khách sẽ lần lượt ăn các đồ ăn ở trên bàn, khi đến vị khách thứ ~i~, họ sẽ ăn hết các đồ ăn ưa thích của họ mà vẫn còn trên bàn tiệc.
• Nếu vị khách đó không ăn được món nào, họ sẽ bỏ về trong tức giận.

Bạn không muốn thấy các vị khách của mình tức giận nên cần tối thiểu số vị khách bỏ về. Vậy có ít nhất bao nhiêu vị khách sẽ tức giận

Input

Dòng đầu tiên gồm 2 số nguyên ~N~ và ~K~: số đồ ăn và số vị khách tham gia bữa tiệc

~K~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u~ và ~v~; 2 vị món ăn mà vị khách đó thích

Output

In ra một số nguyên là số vị khách tức giận ít nhất mà bạn có thể có

Giới hạn

~1 <= N, K <= 10^5~

~1 <= u, v <= N~

Test mẫu

Input

5 4
1 2
4 3
1 4
3 4

Output

1

Có ~N~ tòa nhà chọc trời ở Hà Nội, mỗi tòa nhà có chiều cao của tòa nhà thứ ~i~ là ~h_i~. Hôm nay, tiến sĩ Heinz Doofenshmirtz tự nhiên lại nổi hứng muốn chiếm thành phố Hà Nội, nên ông đã tạo cỗ máy động đất nhằm phá hủy các căn nhà ở đây. Cỗ máy đã bắn ~N-1~ căn nhà đầu tiên, chỉ còn tòa thứ ~N~ đang an toàn. Bạn là một đặc vụ của OWCA xuất phát từ tòa nhà thứ nhất, cần phải đến căn nhà thứ ~N~ để đảm bảo an toàn có thể thực hiện một cú nhảy từ tòa nhà thứ ~i~ đến tòa nhà thứ ~j~ (~i < j~) nếu thỏa mãn một trong các điều kiện sau:

• ~i + 1 = j~
• ~max(h_{i+1}, ..., h_{j-1}) < min(h_i, h_j)~
• ~max(h_i, h_j) < min(h_{i+1}, ..., h_{j-1})~

Hãy tính toán xem bạn cần ít nhất bao nhiêu bước nhảy để đảm bảo an toàn.

Input

Dòng đầu tiên chứa một số nguyên ~N~: số tòa nhà chọc trời ở Hà Nội

Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2,...,h_n~: chiều cao của tòa nhà thứ ~i~.

Output

In ra một số nguyên ~m~ là số lần nháy ít nhất mà bạn cần nhảy.

Giới hạn

~2 <= N <= 3*10^5~

~1 <= h_i <= 10^9~

Test mẫu

Input

5
1 3 1 4 5

Output

3

Bạn được cho một bản đồ của một toà nhà, và được yêu cầu xác đinh số phòng có trong toà nhà đó. Bản đồ có kích thước là ~N * M~ ô vuông, mỗi ô vuông có thể là sàn hoặc tường. Bạn có thể đi lên, xuống, trái, phải trên các ô sàn.

Một phòng trong toà nhà được định nghĩa là phần trong toà nhà với các ô sàn nhà liền kề nhau.

Input

Dòng đầu tiên gồm 2 số nguyên, ~N~ và ~M~: chiều cao và chiều rộng của bản đồ.

~N~ dòng tiếp theo, mỗi dòng chứa ~M~ ký tự mô tả bản đồ: # cho tường và . cho sàn.

Output

Gồm một số nguyên: số phòng có trong toà nhà.

Giới hạn

~1 <= N, M <= 1000~

Test mẫu

Input:

5 8
########
#..#...#
####.#.#
#..#...#
########

Output:

3

Có ~N~ thành phố và ~M~ chuyến bay kết nối giữa chúng. Bạn đang ở thành phố số 1. Nhiệm vụ của bạn là tìm khoảng cách ngắn nhất tới các thành phố còn lại

Input

Dòng đầu tiên chứa hai số nguyên ~N~, ~M~: số thành phố và số chuyến bay giữa chúng.

~M~ dòng tiếp theo, mỗi dòng gốm 3 số nguyên ~a~, ~b~, ~c~, biểu diễn là có một chuyến bay xuất phát tại thành phố ~a~, hạ cánh ở thành phố ~b~ và có độ dài bằng ~c~.

Mỗi chuyến bay là chuyến bay một chiều.

Output

In ra ~N~ số nguyên, khoảng cách từ thành phố thứ nhất tới tất cả ~N~ thành phố.

Giới hạn

~1 <= N <= 10^5~

~1 <= M <= 2*10^5~

~1 <= a, b <= N~

~1 <= c <= 10^9~

Test mẫu

Input:

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

Output:

0 5 2

Bạn đang chơi một trò chơi có ~N~ phòng và ~M~ đường hầm. Số điểm ban đầu của bạn là 0, và mỗi đường hầm bạn đi qua có thể cho bạn một số điểm ~x~. Mọi đường hầm đều là đường một chiều và có thể đi qua nhiều lần.

Nhiệm vụ của bạn là đi từ phòng 1 đến phòng thứ ~N~. Số điểm tối đa mà bạn có thể nhận được là bao nhiêu?

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~: số phòng và số đường hầm có trong trò chơi ~M~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~u, v, w~: biểu diễn có đường hầm đi từ phòng ~u~ đến phòng ~v~ và cho bạn ~w~ điểm

Output

Gồm một số nguyên là kết quả của bài toán. Nếu số điểm bạn nhận được là một số nguyên lớn vô hạn, in ra -1

Giới hạn

~1 <= N <= 2500~

~1 <= M <= 5000~

~1 <= u, v <= N~

~-10^9 <= w <= 10^9~

Test mẫu

Input

4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

Output

5