字母哥站队

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

由于领土纠纷,数字国向字母国宣战。

但是字母国由于平日管理不严,任意两个家族(a,b,c,d….)经常互相发生互殴事件。所以每当小兵们去战场排队的时候不能将互相有冲突的两个家族的小兵安排挨在一起排队,必须踢出一个小兵,以保证这些小兵的军心一致(改变小兵们的前后次序,只能踢出小兵)。

为了保持字母国每次派兵的战斗力可以最高,国王要求字母将军二龙湖彪哥每次踢出最少的小兵。但是彪哥实在是太彪了。。。无法完成这项艰巨而光荣的任务,于是彪哥跪求各位大神帮助他完成这项任务。军情紧急,彪哥给您跪下了~

由于彪哥关怀下属,他知道那两个字母家族有冲突。而且,每个家族最多只有一个敌对家族。

但是,哥是二龙湖的嘛~~~

Input

 

第一行输入原来的小兵序列,第二行输入彪哥知道有冲突家族的对数k

剩下k行的输入哪两个家族有冲突。

Output

 

输出最少踢出多少小兵。

Sample Input

ababa
1
ab

Sample Output

2

Hint

 

Source