Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa ~n~ địa điểm. Biết rằng nếu có đường đi giữa địa điểm ~a~ tới địa điểm ~b~ và từ địa điểm ~b~ tới địa điểm ~c~ thì có thể đi từ ~a~ đến ~c~. Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối ~m~ cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m \le 10^5~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 địa điểm ~u, v \le n~.

Output

• In ra một số ~p~ là số lượng đường đi trực tiếp giữa 2 địa điểm.
• ~p~ dòng sau mỗi dòng in ra 2 số ~u, v~ nghĩa là xây đường đi giữa 2 địa điểm ~u~ và ~v~.

Sample Test

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4

Sau khi Kawashiro xây xong hệ thống cáp treo, cô lại phải tiếp tục xây dựng một số cáp treo nữa để tất cả địa điểm từ 1 đến ~n~ đều có thể đến đền Moriya nằm ở vị trí ~T~.

Input

• Dòng đầu gồm 3 số tự nhiên ~n, m, T \le 100000~.
• ~m~ dòng tiếp theo gồm 2 số ~u, v~ nghĩa là địa điểm ~u, v~ dã được nối bằng cáp treo một chiều.

Output

• Số lượng tối thiểu cáp treo cô cần xây thêm để mọi địa điểm từ 1 đến ~n~ đều đến được đền Moriya ở ~T~.

Sample Test

Input:

6 4 5
1 3
2 3
4 5
6 5

Output:

1

Có 2 vợ chồng nhà ếch nọ bị chia cắt nhau sau khi Cirno đóng băng Hồ Sương Mù. Hồ có thể được thể hiện bằng một hình chữ nhật có ~N~ dòng và ~M~ cột. Một số ô đã bị đóng băng bởi Cirno được thể hiện bằng kí tự ~'X'~, ô không bị đóng băng là thể hiện bằng kí tự ~'.'~ và vị trí 2 chú ếch là kí tự ~'L'~.

Cứ mỗi ngày qua đi những ô bị đóng băng mà kề với ô chứa nước sẽ tan ra. Những chú ếch có thể di chuyển vào những ô không bị đóng băng. Hãy cho biết sau tối thiểu bao nhiêu ngày thì 2 vợ chồng được đoàn tụ.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~1 \le N, M \le 1500~.
• Mỗi dòng trong ~N~ dòng tiếp theo gồm ~M~ kí tự mô tả hồ nước.

Output

• Số ngày tối thiểu để 2 vợ chồng ếch gặp nhau.

Sample Input

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

Sample Output

3

Cho một cây vô hướng ~n~ đỉnh. Trên mỗi đỉnh ~i~ sẽ có một trọng số nguyên ~a_i~. Định nghĩa ~g(u,v)~ là giá trị lớn nhất của trọng số các đỉnh trên đường đi ngắn nhất từ ~u~ đến ~v~. Hãy tính tổng ~g(u,v)~ với mọi cặp ~(1 \le u < v \le n)~.

Input:

• Dòng đầu là số nguyên dương ~n~. ~(2 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên ~a_i. (|a_i| <= 10^6)~.
• ~n-1~ dòng sau mỗi dòng gồm 2 số nguyên ~u,v~ miêu tả cạnh nối giữa 2 đỉnh ~u,v~.

Output:

In ra một số nguyên là kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~.
• Subtask 2: Không có điều kiện gì thêm.

Sample Test

Input:

3
3 2 4
1 2
1 3

Output:

11

Giải thích:

Ta có : ~g(1,2) + g(1,3) + g(2,3) = 3 + 4 + 4 = 11.~

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 4~.