line1 = gets.chomp!
line2 = gets.chomp!
abort "line1 format error" unless line1=~/^\d+ \d+$/
abort "line2 format error" unless line2=~/^[ACDP]+$/

n, m = line1.split.map &:to_i
ss = line2
abort "assert N=|S|" unless ss.size == n

hash = {}
edges = []
m. times do |lop|
    line = gets.chomp!
    abort "line#{3+lop} missing" unless !line.nil?
    abort "line#{3+lop} format error" unless line=~/^\d+ \d+$/
    u, v = line.split.map &:to_i
    abort "line#{3+lop} assert u<v" unless u < v
    abort "line#{3+lop} assert 1<=u<=N" unless 1 <= u && u <= n
    abort "line#{3+lop} assert 1<=v<=N" unless 1 <= v && v <= n
    abort "line#{3+lop}, line#{hash[u*(n+1)+v]} assert multiple edges" unless hash[u*(n+1)+v].nil?
    hash[u*(n+1)+v] = 3+lop
end

assert "too many lines" unless gets.nil?

puts "verified"