Cặp chữ cái cấm

Cho một xâu $s$ gồm các chữ cái Latin in thường. Người ta định nghĩa $k$ cặp chữ cái cấm, mỗi cặp gồm hai chữ cái khác nhau. Một xâu được coi là hợp lệ nếu không có hai chữ cái thuộc cùng một cặp cấm đứng cạnh nhau (cặp cấm không có thứ tự — nếu $ab$ là cặp cấm thì cả "ab" lẫn "ba" đều bị cấm).

Mỗi chữ cái xuất hiện trong không quá một cặp cấm.

Bạn được phép xóa các chữ cái trong $s$; sau khi xóa, các chữ còn lại ghép sát nhau theo thứ tự cũ. Hãy tìm số chữ cái ít nhất cần xóa để xâu thu được không chứa hai chữ cái cùng một cặp cấm đứng cạnh nhau.

Dữ liệu vào

• Dòng đầu chứa xâu $s$ gồm các chữ cái Latin in thường, $1\le |s|\le {10}^5$.
• Dòng thứ hai chứa số nguyên $k$ ($0\le k\le 13$) — số cặp chữ cái cấm.
• $k$ dòng tiếp theo, mỗi dòng chứa đúng hai chữ cái Latin in thường khác nhau (không có dấu cách ở giữa) mô tả một cặp cấm. Mỗi chữ cái xuất hiện trong không quá một cặp.

Dữ liệu ra

In ra một số nguyên duy nhất — số chữ cái ít nhất cần xóa khỏi $s$.

Ràng buộc

• $1\le |s|\le {10}^5$
• $0\le k\le 13$
• Mỗi chữ cái xuất hiện trong không quá một cặp cấm.

Ví dụ