在資訊科學上，A 病毒可以看成一個由 A、U、G、C 這四種字母構成的字串。病毒演化過程中，某些字元可能變異成其他字元。
例如，將 \(AAUGG\) 中的第 3 個位置的 \(U\) 換成 \(C\)，則得到 \(AACGG\)。變異可能發生在多個位置。

有個實驗團隊取得了某種 A 病毒的數個 A 片段樣本，並且掌握到這些樣本演化的親緣關係，
用 (樣本編號，親代編號，A 字串) 的格式記錄，其中「樣本編號」與「親代編號」為兩個整數。
若兩數字相同，則該樣本為演化的源頭。

例如：

(1, 1, AAAA)  
(2, 1, GCAA)

表示樣本 1 的 A 字串為 \(AAAA\)，樣本 2 的為 \(GCAA\)，且樣本 2 是由樣本 1 在兩個位置發生變異演化而來，樣本 1 為演化的源頭。

然而，字串中每個位置的字元無法確定，實驗團隊以 \(@\) 來表示這些字元。換言之，\(@\) 可能為 \(A, U, G, C\) 中的任何一個。

請注意，一個字串中可能有多個 \(@\)，並非代表這些位置的字元是相同的。例如 \(A@C@\) 可能是任何第一個字元為 \(A\) 且第三個字元為 \(C\) 的字串，如：

• \(ACCU\)
• \(AACC\)

團隊猜測演化過程發生的變異總數會盡可能少。請你利用親緣關係，計算最小的變異總數量。

輸入格式

第一行有兩個正整數 \(n\) 與 \(m\)，表示共有 \(n\) 個樣本，由 \(1\) 至 \(n\) 編號；每個樣本之 A 字串長度均為 \(m\)，其中 \(n ≤ 1000\) 且 \(m ≤ 80\)。 接下來 n 行，每行包含以空白間隔的兩個正整數 \(i\) 與 \(j\) 以及一個 A 字串 \(s_i\)，對應一個樣本\((i, j,s_i)\)，\(s_i\) 由 A、U、G、C 與@五種字元所組成。若 \(i=j=1\)，則該樣本即為演化的源頭， 源頭以外的樣本皆恰有一個親代。

輸出格式

輸出最小可能的變異總數。

範例輸入 1

2 3
1 1 AAC
2 1 A@@

範例輸出 1

0

範例輸入 2

6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A

範例輸出 2

1