USACO 2013 - US Open - Hạng Vàng

Trong buổi sinh hoạt đầu năm, cô giáo chủ nhiệm giao cho Công Đức chụp lại một số tấm ảnh kỷ niệm cho lớp ITK19. Công Đức yêu cầu tất cả \(N\) bạn học sinh trong lớp (không tính cậu ấy) xếp thành một hàng và đánh số các bạn từ \(1\) đến \(N\) từ đầu hàng đến cuối hàng. Sau đó, cậu ấy chụp tổng cộng \(M\) tấm ảnh, tấm ảnh thứ \(i\) ghi lại hình ảnh một đoạn con từ học sinh \(a_i\) đến học sinh \(b_i\).

Sau khi quan sát \(M\) tấm ảnh được chụp, cô giáo nhận ra một hiện tượng: trong mỗi tấm ảnh có đúng một học sinh không mặc đồng phục! Vì số ảnh quá lớn nên cô rất ngại rà soát ngược lại từng tấm để điểm tên những học sinh này. Cô liền nhờ Đức lập trình xác định số lượng tối đa các bạn học sinh trong lớp không mặc đồng phục (không tính Đức) theo ràng buộc trên. Các bạn hãy giúp Đức nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M (1 \le/q N \leq 2 \times 10^5, 1 \leq M \leq 10^5)\).

• Dòng thứ \(i\) trong \(M\) dòng sau chứa hai số nguyên dương \(a_i\) và \(b_i\).

Ouput

• Một số nguyên là số lượng lớn nhất có thể các học sinh không mặc đồng phục. Nếu không tìm được nghiệm thoả mãn thì in ra \(−1\).

Example

5 3
1 4
2 5
3 4 

1

Bơm rủ bạn gái đi chơi lễ hội hoa hồng nhân ngày 8/3. Lễ hội được sắp đặt trong một bản đồ gồm \(n\) địa điểm đánh số từ \(1\) tới \(n\) và \(n-1\) con đường đánh số từ \(1\) tới \(n-1\). Con đường thứ \(i\) nối giữa hai địa điểm \(u_i\) và \(v_i\) và cho phép di chuyển giữa hai địa điểm này theo cả hai chiều. Hệ thống đường đi đảm bảo sự đi lại giữa hai địa điểm bất kỳ.

Bơm muốn chọn một hành trình giữa hai địa điểm của lễ hội mà không đi qua con đường nào hai lần. Ngoài ra vì e ngại hành trình có thể khá dài nên Bơm muốn chọn một địa điểm làm nơi nghỉ chân không trùng với nơi bắt đầu và kết thúc hành trình.

Trên mỗi con đường có thể trưng bày một trong hai loại hoa: hồng đỏ hoặc hồng xanh. Bạn gái của Bơm lại yêu cầu một hành trình thỏa mãn: số con đường trưng bày hồng đỏ phải bằng số con đường trưng bày hồng xanh trên phần hành trình từ nơi bắt đầu tới điểm nghỉ chân cũng như trên phần hành trình từ điểm nghỉ chân tới điểm kết thúc.

Yêu cầu

Hãy cho biết có bao nhiêu hành trình thỏa mãn cả yêu cầu của Bơm và bạn gái. Một hành trình là một cặp điểm \((s,t)\) trong đó \(s < t\) cho biết hành trình đó đi từ địa điểm \(s\) tới địa điểm \(t\). Hai hành trình có điểm bắt đầu và kết thúc giống nhau được coi là giống nhau cho dù cách chọn nơi nghỉ chân trên hai cách đi có thể khác nhau.

Input

• Dòng đầu chứa số nguyên dương \(n \leq 10^5\)
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i, v_i, c_i\) cho biết có con đường nối giữa \(u_i\) và \(v_i\) và trên con đường đó trưng bày loại hoa \(c_i\). \(c_i \in \{0,1\}\), \(c_i = 0\) ứng với loại hoa hồng đỏ và \(c_i = 1\) ứng với loại hoa hồng xanh

Output

• Ghi ra một số nguyên duy nhất là số hành trình thỏa mãn cả yêu cầu của Bơm và bạn gái

Example

7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1

1

Những cô bò của Farmer John gần đây nhận được một phiến đá cẩm thạch lớn, nhưng không may, nó có một số khuyết điểm. Để mô tả các khuyết điểm này, ta có thể biểu diễn phiến đá cẩm thạch bằng một lưới vuông \(N \times N\) (\(5 \le N \le 300\)), trong đó ký tự * biểu thị một khuyết điểm và . biểu thị một vùng đá cẩm thạch hoàn hảo.

Những cô bò muốn khắc số “8” lên phiến đá cẩm thạch này (bò rất thích số “8” vì mỗi chân trong số bốn chân của chúng đều có móng chẻ đôi, nên chúng thực sự có thể đếm đến 8 bằng các “ngón chân”). Tuy nhiên, chúng cần bạn giúp xác định vị trí tối ưu cho hình số tám trên phiến đá cẩm thạch. Sau đây là một số tính chất xác định một hình số tám hợp lệ:

• Một hình số tám gồm hai hình chữ nhật, một hình ở trên và một hình ở dưới.
• Cả hình trên lẫn hình dưới đều có ít nhất một ô ở phần bên trong.
• Cạnh dưới của hình chữ nhật trên là một tập con (không nhất thiết là tập con thực sự) của cạnh trên của hình chữ nhật dưới.
• Hình số tám chỉ có thể được khắc trên những vùng hoàn hảo của phiến đá cẩm thạch.

Điểm thẩm mỹ của một hình số tám bằng tích diện tích được bao quanh bởi hai hình chữ nhật của nó. Những cô bò muốn tối đa hóa điểm số này.

Ví dụ, cho phiến đá cẩm thạch sau:

...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............

hình số tám được đặt tối ưu là:

..88888888888..
..8.........8..
..8*******..8..
.*8...*.....8.*
.*8.....*...8*.
..8.*.......8..
..8*...****.8..
.88888888888888
.8**.*..*..*..8
.8.*...**.*...8
*8.*...*......8
.8............8
.8...*..*.....8
.8.......*....8
.88888888888888

Hình chữ nhật trên có diện tích \(6 \times 9 = 54\), còn hình chữ nhật dưới có diện tích \(12 \times 6 = 72\). Vì vậy, điểm thẩm mỹ của nó là \(54 \times 72 = 3888\).

Dữ liệu vào

• Dòng 1 chứa một số nguyên duy nhất \(N\), là độ dài cạnh của phiến đá cẩm thạch.
• Các dòng từ 2 đến \(N+1\): mỗi dòng mô tả một hàng của phiến đá cẩm thạch và chứa \(N\) ký tự, mỗi ký tự là * (một khuyết điểm) hoặc . (một vùng hoàn hảo).

Dữ liệu ra

• Dòng 1 chứa điểm thẩm mỹ cao nhất của một hình số tám không sử dụng bất kỳ ô khuyết điểm nào trên phiến đá cẩm thạch. Nếu không thể tạo được hình số tám nào thì in ra -1.

Ví dụ

15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............

3888

Nguồn

USACO 2013 US Open, Gold — Problem 3: Figure Eight

Tác giả đề: John Pardon, 2010.