Bài tập

An tạo cho mình một mật khẩu bằng cách sinh ra một dãy \(S\) gồm các chữ cái Latin in thường viết liền nhau. Sau đó bạn thực hiện các bước sau:

• Sắp xếp các chữ cái trong mật khẩu theo thứ tự từ điển;

• Trong dãy ký tự đã sắp, An tạo ra một dãy mới \(T\) bằng cách chỉ giữ lại số lượng chữ cái tương ứng với thứ tự của nó trong bảng chữ cái:

• Nếu có nhiều hơn một chữ cái 'a' thì chỉ giữ lại một;

• Nếu có nhiều hơn hai chữ cái 'b' thì chỉ giữ lại hai, ngược lại thì giữ nguyên;
• Nếu có nhiều hơn ba chữ cái 'c' thì chỉ giữ lại ba, ngược lại thì giữ nguyên;
• ...

• Nếu có nhiều hơn 26 chữ cái 'z' thì chỉ giữ lại 26, ngược lại thì giữ nguyên.

• Ghép dãy \(T\) vào sau dãy \(S\) và ghi dãy thu được vào tệp đầu ra.

Sau một thời gian, An không thể tìm ra mật khẩu S của mình nữa.

Yêu cầu: Từ dãy chữ cái đã ghi trong sổ tay của An, hãy giúp An tìm lại mật khẩu (S).

Input

Đọc từ tệp CAU3.INP gồm:

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \leq n \leq 5 \times 10^5)\), là số ký tự của dãy chữ cái trong sổ tay của An;
• Dòng thứ hai chứa dãy chữ cái hợp lệ độ dài \(n\).

Output

Ghi vào tệp CAU3.OUT gồm :

• Một dòng ghi dãy chữ cái Latin in thường là mật khẩu \((S)\) tìm được.

Example

19
abbracadabraabbcdrr

abbracadabra

10
dddddddddd

dddddd

Scoring

• 20% số điểm: mật khẩu chỉ gồm chữ cái 'a';
• 40% số điểm: mật khẩu chỉ gồm các chữ cái giống nhau;
• 40% số điểm còn lại không có ràng buộc gì thêm.

Có \(N\) chiếc đèn được xếp thành một hàng dài trong hành lang. Mỗi đèn chỉ có hai trạng thái: bật (1) hoặc tắt (0). Có một cơ chế đặc biệt cho phép bạn thay đổi trạng thái của một đoạn đèn bằng một trong ba thao tác sau:

• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và tắt toàn bộ các đèn từ \(p\) đến \(q\).
• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và bật toàn bộ các đèn từ \(p\) đến \(q\).
• Chọn hai số nguyên \(p, q\) \((1 \le p \le q \le N)\), và đảo trạng thái toàn bộ các đèn từ \(p\) đến \(q\) (nếu đèn đang bật thì tắt, nếu đang tắt thì bật).

Trạng thái hiện tại của các đèn được mô tả bởi chuỗi nhị phân \(A\) độ dài \(N\), trong đó ký tự thứ \(i\) là 0 nếu đèn thứ \(i\) đang tắt, và 1 nếu đang bật. Trạng thái mong muốn được mô tả bởi chuỗi nhị phân \(B\) độ dài \(N\).

Hãy tính số lượng thao tác ít nhất cần thực hiện để biến chuỗi \(A\) thành \(B\).

\InputFile

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa chuỗi \(A\) gồm đúng \(N\) ký tự 0 hoặc 1.
• Dòng thứ ba chứa chuỗi \(B\) gồm đúng \(N\) ký tự 0 hoặc 1.

\OutputFile

In ra một số nguyên là số lượng thao tác tối thiểu để biến \(A\) thành \(B\).

\Scoring

• Subtask 1 (18%): \(N \le 18\)
• Subtask 2 (20%): \(N \le 2000\)
• Subtask 3 (16%): Chuỗi \(A\) chỉ gồm toàn ký tự 0
• Subtask 4 (46%): Không có ràng buộc bổ sung

\Examples

\beginexample
\exmp
8
11011100
01101001
4

\endexample

\Note

Một cách để thực hiện 4 thao tác như sau:

• Đảo đoạn [1, 4] \(\Rightarrow\) 00101100
• Bật đoạn [2, 2] \(\Rightarrow\) 01101100
• Đảo đoạn [6, 8] \(\Rightarrow\) 01101011.
• Tắt đoạn [6, 7] \(\Rightarrow\) 01101001

Không có cách nào thực hiện ít hơn 4 thao tác.

\endproblem

Cho một đồ thị vô hướng có \(N\) đỉnh và \(M\) cạnh. Sử dụng thuật toán DFS để duyệt qua đồ thị và đếm tổng số lượng thành phần liên thông (Connected Components) có trong đồ thị.

Input

• Dòng đầu tiên là hai số nguyên dương \(N\) và \(M\) (\(1 \leq N \leq 10^5, 0 \leq M \leq 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Output

Một dòng duy nhất chứa số lượng thành phần liên thông.

Example

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

2

Cho một đồ thị có hướng \(G=(V, E)\) gồm \(N\) đỉnh và \(M\) cung. Hai đỉnh \(s\) và \(t\) được cho trước. Một đường đi đơn là một dãy các đỉnh \(P=\langle p_0, p_1, \dots, p_k \rangle\) sao cho \(p_0=s\), \(p_k=t\), \((p_{i-1}, p_i) \in E\), và tất cả các đỉnh trên đường đi đều đôi một khác nhau.

Yêu cầu: Biết rằng tồn tại ít nhất một đường đi từ \(s\) tới \(t\), hãy tìm và chỉ ra đường đi đơn từ \(s\) đến \(t\) có thứ tự từ điển nhỏ nhất. Nếu không tồn tại đường đi, in ra -1.

Một đường đi \(P\) được coi là nhỏ hơn về thứ tự từ điển so với đường đi \(Q\) nếu tại chỉ số đầu tiên mà các đỉnh tương ứng khác nhau, đỉnh của \(P\) có chỉ số nhỏ hơn.

Input

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(s\), \(t\): số lượng đỉnh, số lượng cung, đỉnh xuất phát và đỉnh đích (\(1 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq s, t \leq N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\), thể hiện cho một cung nối từ đỉnh \(u\) đến đỉnh \(v\) trong đồ thị (\(1 \leq u, v \leq N\)).

Output

Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi đơn giản có thứ tự từ điển nhỏ nhất tìm được, bắt đầu từ đỉnh \(s\) và kết thúc ở đỉnh \(t\), cách nhau một dấu cách. Nếu không tồn tại đường đi, in ra -1.

Example

8 11 1 8
1 2
2 3
2 4
3 1
7 5
3 7
4 6
6 2
5 8
1 8
6 4

1 2 3 7 5 8