Lights
TopCoder TCO2012 Round 1A
Time Limit: 0.1s, Memory Limit: 64MiB
В къщата на Ели има N електрически крушки. Някои от тях са включени, докато други не са. Момичето иска да изключи всички крушки за идващия Час на Земята.

Нейната къща има странна система от M ключа за управление на светлината. Всеки ключ променя състоянието на подмножество от крушките (възможно е на никоя или на всички). Това означава, че ако тя реши да ползва даден ключ, всички крушки, които са свързани с него, се изключват, ако са били включени, или се включват, ако са били изключени. Ели знае, че никоя крушка не е вързана за повече от два ключа. Помогнете на момичето да намери минималния брой ключове, които трябва да ползва, за да изключи всички крушки.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N - броя крушки в къщата на Ели. Следва ред с N символа 'Y' и 'N', указващ началната конфигурация на крушките ('Y' ако е включена и 'N' ако не е). На третия ред е зададено цялото число M – броя ключове за управление. Следват M реда, всеки съдържащ по N символа. Символът в i-тия от тях ред, j-та колона е 'Y', ако i-тият ключ променя състоянието на j-тата крушка, или 'N' в противен случай.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния брой ключове, които Ели трябва да ползва за да изгаси всички крушки. Ако това е невъзможно, вместо това изведете -1.
Ограничения
  • 1 ≤ N, M ≤ 50
  • Във всяка колона ще има най-много два символа 'Y'.
Примерен Вход Примерен Изход
6 YNYNNN 5 YNNYNY NYYYNN YNYNYN NNNNYN NYNNNY 2
3 YYN 2 YNY NYN -1
В първия пример един от възможните начини, по които Ели може да изгаси всички крушки, е да използва ключ 0, след това ключ 4 и накрая ключ 1. Вместо това, обаче, тя може да ползва само ключовете 2 и 3, постигайки същия резултат само с две цъкания.
Във втория пример, независимо как Ели ползва ключовете, тя не може да изключи крушките.
Мрън!