using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

            List<string> cidades = new List<string>(645);

            #region addCidades

            cidades.Add("ADAMANTINA");

            cidades.Add("ADOLFO");

            cidades.Add("AGUAI");

            cidades.Add("AGUAS DA PRATA");

            cidades.Add("AGUAS DE LINDOIA");

            cidades.Add("AGUAS DE SANTA BARBARA");

            cidades.Add("AGUAS DE SAO PEDRO");

            cidades.Add("AGUDOS");

            cidades.Add("ALAMBARI");

            cidades.Add("ALFREDO MARCONDES");

            cidades.Add("ALTAIR");

            cidades.Add("ALTINOPOLIS");

            cidades.Add("ALTO ALEGRE");

            cidades.Add("ALUMINIO");

            cidades.Add("ALVARES FLORENCE");

            cidades.Add("ALVARES MACHADO");

            cidades.Add("ALVARO DE CARVALHO");

            cidades.Add("ALVINLANDIA");

            cidades.Add("AMERICANA");

            cidades.Add("AMERICO BRASILIENSE");

            cidades.Add("AMERICO DE CAMPOS");

            cidades.Add("AMPARO");

            cidades.Add("ANALANDIA");

            cidades.Add("ANDRADINA");

            cidades.Add("ANGATUBA");

            cidades.Add("ANHEMBI");

            cidades.Add("ANHUMAS");

            cidades.Add("APARECIDA");

            cidades.Add("APARECIDA D'OESTE");

            cidades.Add("APIAI");

            cidades.Add("ARACARIGUAMA");

            cidades.Add("ARACATUBA");

            cidades.Add("ARACOIABA DA SERRA");

            cidades.Add("ARAMINA");

            cidades.Add("ARANDU");

            cidades.Add("ARAPEI");

            cidades.Add("ARARAQUARA");

            cidades.Add("ARARAS");

            cidades.Add("ARCO-IRIS");

            cidades.Add("AREALVA");

            cidades.Add("AREIAS");

            cidades.Add("AREIOPOLIS");

            cidades.Add("ARIRANHA");

            cidades.Add("ARTUR NOGUEIRA");

            cidades.Add("ARUJA");

            cidades.Add("ASPASIA");

            cidades.Add("ASSIS");

            cidades.Add("ATIBAIA");

            cidades.Add("AURIFLAMA");

            cidades.Add("AVAI");

            cidades.Add("AVANHANDAVA");

            cidades.Add("AVARE");

            cidades.Add("BADY BASSITT");

            cidades.Add("BALBINOS");

            cidades.Add("BALSAMO");

            cidades.Add("BANANAL");

            cidades.Add("BARAO DE ANTONINA");

            cidades.Add("BARBOSA");

            cidades.Add("BARIRI");

            cidades.Add("BARRA BONITA");

            cidades.Add("BARRA DO CHAPEU");

            cidades.Add("BARRA DO TURVO");

            cidades.Add("BARRETOS");

            cidades.Add("BARRINHA");

            cidades.Add("BARUERI");

            cidades.Add("BASTOS");

            cidades.Add("BATATAIS");

            cidades.Add("BAURU");

            cidades.Add("BEBEDOURO");

            cidades.Add("BENTO DE ABREU");

            cidades.Add("BERNARDINO DE CAMPOS");

            cidades.Add("BERTIOGA");

            cidades.Add("BILAC");

            cidades.Add("BIRIGUI");

            cidades.Add("BIRITIBA-MIRIM");

            cidades.Add("BOA ESPERANCA DO SUL");

            cidades.Add("BOCAINA");

            cidades.Add("BOFETE");

            cidades.Add("BOITUVA");

            cidades.Add("BOM JESUS DOS PERDOES");

            cidades.Add("BOM SUCESSO DE ITARARE");

            cidades.Add("BORA");

            cidades.Add("BORACEIA");

            cidades.Add("BORBOREMA");

            cidades.Add("BOREBI");

            cidades.Add("BOTUCATU");

            cidades.Add("BRAGANCA PAULISTA");

            cidades.Add("BRAUNA");

            cidades.Add("BREJO ALEGRE");

            cidades.Add("BRODOSQUI");

            cidades.Add("BROTAS");

            cidades.Add("BURI");

            cidades.Add("BURITAMA");

            cidades.Add("BURITIZAL");

            cidades.Add("CABRALIA PAULISTA");

            cidades.Add("CABREUVA");

            cidades.Add("CACAPAVA");

            cidades.Add("CACHOEIRA PAULISTA");

            cidades.Add("CACONDE");

            cidades.Add("CAFELANDIA");

            cidades.Add("CAIABU");

            cidades.Add("CAIEIRAS");

            cidades.Add("CAIUA");

            cidades.Add("CAJAMAR");

            cidades.Add("CAJATI");

            cidades.Add("CAJOBI");

            cidades.Add("CAJURU");

            cidades.Add("CAMPINA DO MONTE ALEGRE");

            cidades.Add("CAMPINAS");

            cidades.Add("CAMPO LIMPO PAULISTA");

            cidades.Add("CAMPOS DO JORDAO");

            cidades.Add("CAMPOS NOVOS PAULISTA");

            cidades.Add("CANANEIA");

            cidades.Add("CANAS");

            cidades.Add("CANDIDO MOTA");

            cidades.Add("CANDIDO RODRIGUES");

            cidades.Add("CANITAR");

            cidades.Add("CAPAO BONITO");

            cidades.Add("CAPELA DO ALTO");

            cidades.Add("CAPIVARI");

            cidades.Add("CARAGUATATUBA");

            cidades.Add("CARAPICUIBA");

            cidades.Add("CARDOSO");

            cidades.Add("CASA BRANCA");

            cidades.Add("CASSIA DOS COQUEIROS");

            cidades.Add("CASTILHO");

            cidades.Add("CATANDUVA");

            cidades.Add("CATIGUA");

            cidades.Add("CEDRAL");

            cidades.Add("CERQUEIRA CESAR");

            cidades.Add("CERQUILHO");

            cidades.Add("CESARIO LANGE");

            cidades.Add("CHARQUEADA");

            cidades.Add("CHAVANTES");

            cidades.Add("CLEMENTINA");

            cidades.Add("COLINA");

            cidades.Add("COLOMBIA");

            cidades.Add("CONCHAL");

            cidades.Add("CONCHAS");

            cidades.Add("CORDEIROPOLIS");

            cidades.Add("COROADOS");

            cidades.Add("CORONEL MACEDO");

            cidades.Add("CORUMBATAI");

            cidades.Add("COSMOPOLIS");

            cidades.Add("COSMORAMA");

            cidades.Add("COTIA");

            cidades.Add("CRAVINHOS");

            cidades.Add("CRISTAIS PAULISTA");

            cidades.Add("CRUZALIA");

            cidades.Add("CRUZEIRO");

            cidades.Add("CUBATAO");

            cidades.Add("CUNHA");

            cidades.Add("DESCALVADO");

            cidades.Add("DIADEMA");

            cidades.Add("DIRCE REIS");

            cidades.Add("DIVINOLANDIA");

            cidades.Add("DOBRADA");

            cidades.Add("DOIS CORREGOS");

            cidades.Add("DOLCINOPOLIS");

            cidades.Add("DOURADO");

            cidades.Add("DRACENA");

            cidades.Add("DUARTINA");

            cidades.Add("DUMONT");

            cidades.Add("ECHAPORA");

            cidades.Add("ELDORADO");

            cidades.Add("ELIAS FAUSTO");

            cidades.Add("ELISIARIO");

            cidades.Add("EMBAUBA");

            cidades.Add("EMBU");

            cidades.Add("EMBU-GUACU");

            cidades.Add("EMILIANOPOLIS");

            cidades.Add("ENGENHEIRO COELHO");

            cidades.Add("ESPIRITO SANTO DO PINHAL");

            cidades.Add("ESPIRITO SANTO DO TURVO");

            cidades.Add("ESTIVA GERBI");

            cidades.Add("ESTRELA D'OESTE");

            cidades.Add("ESTRELA DO NORTE");

            cidades.Add("EUCLIDES DA CUNHA PAULISTA");

            cidades.Add("FARTURA");

            cidades.Add("FERNANDO PRESTES");

            cidades.Add("FERNANDOPOLIS");

            cidades.Add("FERNAO");

            cidades.Add("FERRAZ DE VASCONCELOS");

            cidades.Add("FLORA RICA");

            cidades.Add("FLOREAL");

            cidades.Add("FLORIDA PAULISTA");

            cidades.Add("FLORINIA");

            cidades.Add("FRANCA");

            cidades.Add("FRANCISCO MORATO");

            cidades.Add("FRANCO DA ROCHA");

            cidades.Add("GABRIEL MONTEIRO");

            cidades.Add("GALIA");

            cidades.Add("GARCA");

            cidades.Add("GASTAO VIDIGAL");

            cidades.Add("GAVIAO PEIXOTO");

            cidades.Add("GENERAL SALGADO");

            cidades.Add("GETULINA");

            cidades.Add("GLICERIO");

            cidades.Add("GUAICARA");

            cidades.Add("GUAIMBE");

            cidades.Add("GUAIRA");

            cidades.Add("GUAPIACU");

            cidades.Add("GUAPIARA");

            cidades.Add("GUARA");

            cidades.Add("GUARACAI");

            cidades.Add("GUARACI");

            cidades.Add("GUARANI D'OESTE");

            cidades.Add("GUARANTA");

            cidades.Add("GUARARAPES");

            cidades.Add("GUARAREMA");

            cidades.Add("GUARATINGUETA");

            cidades.Add("GUAREI");

            cidades.Add("GUARIBA");

            cidades.Add("GUARUJA");

            cidades.Add("GUARULHOS");

            cidades.Add("GUATAPARA");

            cidades.Add("GUZOLANDIA");

            cidades.Add("HERCULANDIA");

            cidades.Add("HOLAMBRA");

            cidades.Add("HORTOLANDIA");

            cidades.Add("IACANGA");

            cidades.Add("IACRI");

            cidades.Add("IARAS");

            cidades.Add("IBATE");

            cidades.Add("IBIRA");

            cidades.Add("IBIRAREMA");

            cidades.Add("IBITINGA");

            cidades.Add("IBIUNA");

            cidades.Add("ICEM");

            cidades.Add("IEPE");

            cidades.Add("IGARACU DO TIETE");

            cidades.Add("IGARAPAVA");

            cidades.Add("IGARATA");

            cidades.Add("IGUAPE");

            cidades.Add("ILHA COMPRIDA");

            cidades.Add("ILHA SOLTEIRA");

            cidades.Add("ILHABELA");

            cidades.Add("INDAIATUBA");

            cidades.Add("INDIANA");

            cidades.Add("INDIAPORA");

            cidades.Add("INUBIA PAULISTA");

            cidades.Add("IPAUCU");

            cidades.Add("IPERO");

            cidades.Add("IPEUNA");

            cidades.Add("IPIGUA");

            cidades.Add("IPORANGA");

            cidades.Add("IPUA");

            cidades.Add("IRACEMAPOLIS");

            cidades.Add("IRAPUA");

            cidades.Add("IRAPURU");

            cidades.Add("ITABERA");

            cidades.Add("ITAI");

            cidades.Add("ITAJOBI");

            cidades.Add("ITAJU");

            cidades.Add("ITANHAEM");

            cidades.Add("ITAOCA");

            cidades.Add("ITAPECERICA DA SERRA");

            cidades.Add("ITAPETININGA");

            cidades.Add("ITAPEVA");

            cidades.Add("ITAPEVI");

            cidades.Add("ITAPIRA");

            cidades.Add("ITAPIRAPUA PAULISTA");

            cidades.Add("ITAPOLIS");

            cidades.Add("ITAPORANGA");

            cidades.Add("ITAPUI");

            cidades.Add("ITAPURA");

            cidades.Add("ITAQUAQUECETUBA");

            cidades.Add("ITARARE");

            cidades.Add("ITARIRI");

            cidades.Add("ITATIBA");

            cidades.Add("ITATINGA");

            cidades.Add("ITIRAPINA");

            cidades.Add("ITIRAPUA");

            cidades.Add("ITOBI");

            cidades.Add("ITU");

            cidades.Add("ITUPEVA");

            cidades.Add("ITUVERAVA");

            cidades.Add("JABORANDI");

            cidades.Add("JABOTICABAL");

            cidades.Add("JACAREI");

            cidades.Add("JACI");

            cidades.Add("JACUPIRANGA");

            cidades.Add("JAGUARIUNA");

            cidades.Add("JALES");

            cidades.Add("JAMBEIRO");

            cidades.Add("JANDIRA");

            cidades.Add("JARDINOPOLIS");

            cidades.Add("JARINU");

            cidades.Add("JAU");

            cidades.Add("JERIQUARA");

            cidades.Add("JOANOPOLIS");

            cidades.Add("JOAO RAMALHO");

            cidades.Add("JOSE BONIFACIO");

            cidades.Add("JULIO MESQUITA");

            cidades.Add("JUMIRIM");

            cidades.Add("JUNDIAI");

            cidades.Add("JUNQUEIROPOLIS");

            cidades.Add("JUQUIA");

            cidades.Add("JUQUITIBA");

            cidades.Add("LAGOINHA");

            cidades.Add("LARANJAL PAULISTA");

            cidades.Add("LAVINIA");

            cidades.Add("LAVRINHAS");

            cidades.Add("LEME");

            cidades.Add("LENCOIS PAULISTA");

            cidades.Add("LIMEIRA");

            cidades.Add("LINDOIA");

            cidades.Add("LINS");

            cidades.Add("LORENA");

            cidades.Add("LOURDES");

            cidades.Add("LOUVEIRA");

            cidades.Add("LUCELIA");

            cidades.Add("LUCIANOPOLIS");

            cidades.Add("LUIS ANTONIO");

            cidades.Add("LUIZIANIA");

            cidades.Add("LUPERCIO");

            cidades.Add("LUTECIA");

            cidades.Add("MACATUBA");

            cidades.Add("MACAUBAL");

            cidades.Add("MACEDONIA");

            cidades.Add("MAGDA");

            cidades.Add("MAIRINQUE");

            cidades.Add("MAIRIPORA");

            cidades.Add("MANDURI");

            cidades.Add("MARABA PAULISTA");

            cidades.Add("MARACAI");

            cidades.Add("MARAPOAMA");

            cidades.Add("MARIAPOLIS");

            cidades.Add("MARILIA");

            cidades.Add("MARINOPOLIS");

            cidades.Add("MARTINOPOLIS");

            cidades.Add("MATAO");

            cidades.Add("MAUA");

            cidades.Add("MENDONCA");

            cidades.Add("MERIDIANO");

            cidades.Add("MESOPOLIS");

            cidades.Add("MIGUELOPOLIS");

            cidades.Add("MINEIROS DO TIETE");

            cidades.Add("MIRA ESTRELA");

            cidades.Add("MIRACATU");

            cidades.Add("MIRANDOPOLIS");

            cidades.Add("MIRANTE DO PARANAPANEMA");

            cidades.Add("MIRASSOL");

            cidades.Add("MIRASSOLANDIA");

            cidades.Add("MOCOCA");

            cidades.Add("MOGI GUACU");

            cidades.Add("MOJI-MIRIM");

            cidades.Add("MOJI DAS CRUZES");

            cidades.Add("MOMBUCA");

            cidades.Add("MONCOES");

            cidades.Add("MONGAGUA");

            cidades.Add("MONTE ALEGRE DO SUL");

            cidades.Add("MONTE ALTO");

            cidades.Add("MONTE APRAZIVEL");

            cidades.Add("MONTE AZUL PAULISTA");

            cidades.Add("MONTE CASTELO");

            cidades.Add("MONTE MOR");

            cidades.Add("MONTEIRO LOBATO");

            cidades.Add("MORRO AGUDO");

            cidades.Add("MORUNGABA");

            cidades.Add("MOTUCA");

            cidades.Add("MURUTINGA DO SUL");

            cidades.Add("NANTES");

            cidades.Add("NARANDIBA");

            cidades.Add("NATIVIDADE DA SERRA");

            cidades.Add("NAZARE PAULISTA");

            cidades.Add("NEVES PAULISTA");

            cidades.Add("NHANDEARA");

            cidades.Add("NIPOA");

            cidades.Add("NOVA ALIANCA");

            cidades.Add("NOVA CAMPINA");

            cidades.Add("NOVA CANAA PAULISTA");

            cidades.Add("NOVA CASTILHO");

            cidades.Add("NOVA EUROPA");

            cidades.Add("NOVA GRANADA");

            cidades.Add("NOVA GUATAPORANGA");

            cidades.Add("NOVA INDEPENDENCIA");

            cidades.Add("NOVA LUZITANIA");

            cidades.Add("NOVA ODESSA");

            cidades.Add("NOVAIS");

            cidades.Add("NOVO HORIZONTE");

            cidades.Add("NUPORANGA");

            cidades.Add("OCAUCU");

            cidades.Add("OLEO");

            cidades.Add("OLIMPIA");

            cidades.Add("ONDA VERDE");

            cidades.Add("ORIENTE");

            cidades.Add("ORINDIUVA");

            cidades.Add("ORLANDIA");

            cidades.Add("OSASCO");

            cidades.Add("OSCAR BRESSANE");

            cidades.Add("OSVALDO CRUZ");

            cidades.Add("OURINHOS");

            cidades.Add("OURO VERDE");

            cidades.Add("OUROESTE");

            cidades.Add("PACAEMBU");

            cidades.Add("PALESTINA");

            cidades.Add("PALMARES PAULISTA");

            cidades.Add("PALMEIRA D'OESTE");

            cidades.Add("PALMITAL");

            cidades.Add("PANORAMA");

            cidades.Add("PARAGUACU PAULISTA");

            cidades.Add("PARAIBUNA");

            cidades.Add("PARAISO");

            cidades.Add("PARANAPANEMA");

            cidades.Add("PARANAPUA");

            cidades.Add("PARAPUA");

            cidades.Add("PARDINHO");

            cidades.Add("PARIQUERA-ACU");

            cidades.Add("PARISI");

            cidades.Add("PATROCINIO PAULISTA");

            cidades.Add("PAULICEIA");

            cidades.Add("PAULINIA");

            cidades.Add("PAULISTANIA");

            cidades.Add("PAULO DE FARIA");

            cidades.Add("PEDERNEIRAS");

            cidades.Add("PEDRA BELA");

            cidades.Add("PEDRANOPOLIS");

            cidades.Add("PEDREGULHO");

            cidades.Add("PEDREIRA");

            cidades.Add("PEDRINHAS PAULISTA");

            cidades.Add("PEDRO DE TOLEDO");

            cidades.Add("PENAPOLIS");

            cidades.Add("PEREIRA BARRETO");

            cidades.Add("PEREIRAS");

            cidades.Add("PERUIBE");

            cidades.Add("PIACATU");

            cidades.Add("PIEDADE");

            cidades.Add("PILAR DO SUL");

            cidades.Add("PINDAMONHANGABA");

            cidades.Add("PINDORAMA");

            cidades.Add("PINHALZINHO");

            cidades.Add("PIQUEROBI");

            cidades.Add("PIQUETE");

            cidades.Add("PIRACAIA");

            cidades.Add("PIRACICABA");

            cidades.Add("PIRAJU");

            cidades.Add("PIRAJUI");

            cidades.Add("PIRANGI");

            cidades.Add("PIRAPORA DO BOM JESUS");

            cidades.Add("PIRAPOZINHO");

            cidades.Add("PIRASSUNUNGA");

            cidades.Add("PIRATININGA");

            cidades.Add("PITANGUEIRAS");

            cidades.Add("PLANALTO");

            cidades.Add("PLATINA");

            cidades.Add("POA");

            cidades.Add("POLONI");

            cidades.Add("POMPEIA");

            cidades.Add("PONGAI");

            cidades.Add("PONTAL");

            cidades.Add("PONTALINDA");

            cidades.Add("PONTES GESTAL");

            cidades.Add("POPULINA");

            cidades.Add("PORANGABA");

            cidades.Add("PORTO FELIZ");

            cidades.Add("PORTO FERREIRA");

            cidades.Add("POTIM");

            cidades.Add("POTIRENDABA");

            cidades.Add("PRACINHA");

            cidades.Add("PRADOPOLIS");

            cidades.Add("PRAIA GRANDE");

            cidades.Add("PRATANIA");

            cidades.Add("PRESIDENTE ALVES");

            cidades.Add("PRESIDENTE BERNARDES");

            cidades.Add("PRESIDENTE EPITACIO");

            cidades.Add("PRESIDENTE PRUDENTE");

            cidades.Add("PRESIDENTE VENCESLAU");

            cidades.Add("PROMISSAO");

            cidades.Add("QUADRA");

            cidades.Add("QUATA");

            cidades.Add("QUEIROZ");

            cidades.Add("QUELUZ");

            cidades.Add("QUINTANA");

            cidades.Add("RAFARD");

            cidades.Add("RANCHARIA");

            cidades.Add("REDENCAO DA SERRA");

            cidades.Add("REGENTE FEIJO");

            cidades.Add("REGINOPOLIS");

            cidades.Add("REGISTRO");

            cidades.Add("RESTINGA");

            cidades.Add("RIBEIRA");

            cidades.Add("RIBEIRAO BONITO");

            cidades.Add("RIBEIRAO BRANCO");

            cidades.Add("RIBEIRAO CORRENTE");

            cidades.Add("RIBEIRAO DO SUL");

            cidades.Add("RIBEIRAO DOS INDIOS");

            cidades.Add("RIBEIRAO GRANDE");

            cidades.Add("RIBEIRAO PIRES");

            cidades.Add("RIBEIRAO PRETO");

            cidades.Add("RIFAINA");

            cidades.Add("RINCAO");

            cidades.Add("RINOPOLIS");

            cidades.Add("RIO CLARO");

            cidades.Add("RIO DAS PEDRAS");

            cidades.Add("RIO GRANDE DA SERRA");

            cidades.Add("RIOLANDIA");

            cidades.Add("RIVERSUL");

            cidades.Add("ROSANA");

            cidades.Add("ROSEIRA");

            cidades.Add("RUBIACEA");

            cidades.Add("RUBINEIA");

            cidades.Add("SABINO");

            cidades.Add("SAGRES");

            cidades.Add("SALES");

            cidades.Add("SALES OLIVEIRA");

            cidades.Add("SALESOPOLIS");

            cidades.Add("SALMOURAO");

            cidades.Add("SALTINHO");

            cidades.Add("SALTO");

            cidades.Add("SALTO DE PIRAPORA");

            cidades.Add("SALTO GRANDE");

            cidades.Add("SANDOVALINA");

            cidades.Add("SANTA ADELIA");

            cidades.Add("SANTA ALBERTINA");

            cidades.Add("SANTA BARBARA D'OESTE");

            cidades.Add("SANTA BRANCA");

            cidades.Add("SANTA CLARA D'OESTE");

            cidades.Add("SANTA CRUZ DA CONCEICAO");

            cidades.Add("SANTA CRUZ DA ESPERANCA");

            cidades.Add("SANTA CRUZ DAS PALMEIRAS");

            cidades.Add("SANTA CRUZ DO RIO PARDO");

            cidades.Add("SANTA ERNESTINA");

            cidades.Add("SANTA FE DO SUL");

            cidades.Add("SANTA GERTRUDES");

            cidades.Add("SANTA ISABEL");

            cidades.Add("SANTA LUCIA");

            cidades.Add("SANTA MARIA DA SERRA");

            cidades.Add("SANTA MERCEDES");

            cidades.Add("SANTA RITA D'OESTE");

            cidades.Add("SANTA RITA DO PASSA QUATRO");

            cidades.Add("SANTA ROSA DE VITERBO");

            cidades.Add("SANTA SALETE");

            cidades.Add("SANTANA DA PONTE PENSA");

            cidades.Add("SANTANA DE PARNAIBA");

            cidades.Add("SANTO ANASTACIO");

            cidades.Add("SANTO ANDRE");

            cidades.Add("SANTO ANTONIO DA ALEGRIA");

            cidades.Add("SANTO ANTONIO DE POSSE");

            cidades.Add("SANTO ANTONIO DO ARACANGUA");

            cidades.Add("SANTO ANTONIO DO JARDIM");

            cidades.Add("SANTO ANTONIO DO PINHAL");

            cidades.Add("SANTO EXPEDITO");

            cidades.Add("SANTOPOLIS DO AGUAPEI");

            cidades.Add("SANTOS");

            cidades.Add("SAO BENTO DO SAPUCAI");

            cidades.Add("SAO BERNARDO DO CAMPO");

            cidades.Add("SAO CAETANO DO SUL");

            cidades.Add("SAO CARLOS");

            cidades.Add("SAO FRANCISCO");

            cidades.Add("SAO JOAO DA BOA VISTA");

            cidades.Add("SAO JOAO DAS DUAS PONTES");

            cidades.Add("SAO JOAO DE IRACEMA");

            cidades.Add("SAO JOAO DO PAU D'ALHO");

            cidades.Add("SAO JOAQUIM DA BARRA");

            cidades.Add("SAO JOSE DA BELA VISTA");

            cidades.Add("SAO JOSE DO BARREIRO");

            cidades.Add("SAO JOSE DO RIO PARDO");

            cidades.Add("SAO JOSE DO RIO PRETO");

            cidades.Add("SAO JOSE DOS CAMPOS");

            cidades.Add("SAO LOURENCO DA SERRA");

            cidades.Add("SAO LUIS DO PARAITINGA");

            cidades.Add("SAO MANUEL");

            cidades.Add("SAO MIGUEL ARCANJO");

            cidades.Add("SAO PAULO");

            cidades.Add("SAO PEDRO");

            cidades.Add("SAO PEDRO DO TURVO");

            cidades.Add("SAO ROQUE");

            cidades.Add("SAO SEBASTIAO");

            cidades.Add("SAO SEBASTIAO DA GRAMA");

            cidades.Add("SAO SIMAO");

            cidades.Add("SAO VICENTE");

            cidades.Add("SARAPUI");

            cidades.Add("SARUTAIA");

            cidades.Add("SEBASTIANOPOLIS DO SUL");

            cidades.Add("SERRA AZUL");

            cidades.Add("SERRA NEGRA");

            cidades.Add("SERRANA");

            cidades.Add("SERTAOZINHO");

            cidades.Add("SETE BARRAS");

            cidades.Add("SEVERINIA");

            cidades.Add("SILVEIRAS");

            cidades.Add("SOCORRO");

            cidades.Add("SOROCABA");

            cidades.Add("SUD MENNUCCI");

            cidades.Add("SUMARE");

            cidades.Add("SUZANAPOLIS");

            cidades.Add("SUZANO");

            cidades.Add("TABAPUA");

            cidades.Add("TABATINGA");

            cidades.Add("TABOAO DA SERRA");

            cidades.Add("TACIBA");

            cidades.Add("TAGUAI");

            cidades.Add("TAIACU");

            cidades.Add("TAIUVA");

            cidades.Add("TAMBAU");

            cidades.Add("TANABI");

            cidades.Add("TAPIRAI");

            cidades.Add("TAPIRATIBA");

            cidades.Add("TAQUARAL");

            cidades.Add("TAQUARITINGA");

            cidades.Add("TAQUARITUBA");

            cidades.Add("TAQUARIVAI");

            cidades.Add("TARABAI");

            cidades.Add("TARUMA");

            cidades.Add("TATUI");

            cidades.Add("TAUBATE");

            cidades.Add("TEJUPA");

            cidades.Add("TEODORO SAMPAIO");

            cidades.Add("TERRA ROXA");

            cidades.Add("TIETE");

            cidades.Add("TIMBURI");

            cidades.Add("TORRE DE PEDRA");

            cidades.Add("TORRINHA");

            cidades.Add("TRABIJU");

            cidades.Add("TREMEMBE");

            cidades.Add("TRES FRONTEIRAS");

            cidades.Add("TUIUTI");

            cidades.Add("TUPA");

            cidades.Add("TUPI PAULISTA");

            cidades.Add("TURIUBA");

            cidades.Add("TURMALINA");

            cidades.Add("UBARANA");

            cidades.Add("UBATUBA");

            cidades.Add("UBIRAJARA");

            cidades.Add("UCHOA");

            cidades.Add("UNIAO PAULISTA");

            cidades.Add("URANIA");

            cidades.Add("URU");

            cidades.Add("URUPES");

            cidades.Add("VALENTIM GENTIL");

            cidades.Add("VALINHOS");

            cidades.Add("VALPARAISO");

            cidades.Add("VARGEM");

            cidades.Add("VARGEM GRANDE DO SUL");

            cidades.Add("VARGEM GRANDE PAULISTA");

            cidades.Add("VARZEA PAULISTA");

            cidades.Add("VERA CRUZ");

            cidades.Add("VINHEDO");

            cidades.Add("VIRADOURO");

            cidades.Add("VISTA ALEGRE DO ALTO");

            cidades.Add("VITORIA BRASIL");

            cidades.Add("VOTORANTIM");

            cidades.Add("VOTUPORANGA");

            cidades.Add("ZACARIAS");

            #endregion

​

            //Primeiro a lista é ordenada por ordem alfabética, fazendo com que a sigla SAL seja gerada para a cidade SALES e não para a cidade SALTO.

​

            Dictionary<string, string> siglas = new Dictionary<string, string>();

            foreach (string c in cidades)

            {

                string[] cs = c.Replace("'", " ").Replace("-"," ").Split(' '); //Depois, vamos separar cada nome em palavras com o `Split(' ')`, observando que as cidades com hifén ou apóstrofo também são separadas em palavras.

                bool sucesso = false;

                string sigla = null;

                for (int i = 0; i < cs.Length && !sucesso; i++) //Percorrer cada palavra

                {

                    for (int j = 0; j < cs[i].Length && !sucesso; j++) //Percorrer cada letra da palavra atual (i)

                    {

                        sigla = cs[i][j].ToString(); //Primeira letra da sigla

​

                        for (int k = i+1; k < cs.Length && !sucesso; k++) //Se há mais palavras depois da palavra atual (i), entra no for

                        {

                            for (int l = 0; l < cs[k].Length && !sucesso; l++) //Percorre cada letra da palavra (k)

                            {

                                sigla = cs[i][j].ToString() + cs[k][l].ToString(); //Segunda letra da sigla

​

                                for (int m = cs.Length-1; m > k  && !sucesso; m--) //Se há mais palavras além da palavra (k), entra no for

                                {

                                    for (int n = 0; n < cs[m].Length && !sucesso; n++) //Percorre cada letra da palavra (m)

                                    {

                                        sigla = cs[i][j].ToString() + cs[k][l].ToString() + cs[m][n].ToString(); //Terceira letra da sigla

​

                                        if (!siglas.ContainsKey(sigla)) //Se a sigla ainda não foi utilizada

                                        {

                                            siglas.Add(sigla, c); //Adiciona no dicionário

                                            sucesso = true; //Marca a flag como sucesso pra sair de todos os outros for

                                        }

                                    }

                                }

​

                                for (int m = l+1; m < cs[k].Length && !sucesso; m++) //Se não gerou a terceira letra com a palavra m, percorre as letras seguintes à (l) da palavra (k)

                                {

                                    sigla = cs[i][j].ToString() + cs[k][l].ToString() + cs[k][m].ToString(); //Terceira letra da sigla

​

                                    if (!siglas.ContainsKey(sigla)) //Se a sigla ainda não foi utilizada

                                    {

                                        siglas.Add(sigla, c); //Adiciona no dicionário

                                        sucesso = true; //Marca a flag como sucesso pra sair de todos os outros for

                                    }

                                }

​

                            }

                        }

​

​

                        for (int m = j + 1; m < cs[i].Length && !sucesso; m++) //Se não gerou a segunda letra com a palavra (k) percorre a palavra [i]

                        {

                            if (m + 1 < cs[i].Length) //Dá preferência a letra seguinte se existir

                            {

                                sigla = cs[i][j].ToString() + cs[i][m].ToString() + cs[i][m + 1].ToString(); //Compoe a sigla com a segunda (m) e terceira letra (m+1)

​

                                if (!siglas.ContainsKey(sigla)) //Se a sigla ainda não foi utilizada

                                {

                                    siglas.Add(sigla, c); //Adiciona no dicionário

                                    sucesso = true; //Marca a flag como sucesso pra sair de todos os outros for

                                }

                            }

                            for (int n = cs[i].Length - 1; n >= 0 && !sucesso; n--) //Percorre a palavra (i) no sentido inverso para gerar a terceira letra

                            {

                                sigla = cs[i][j].ToString() + cs[i][m].ToString() + cs[i][n].ToString(); //Compoe a sigla com a segunda (m) e terceira letra (n)

​

                                if (!siglas.ContainsKey(sigla)) //Se a sigla ainda não foi utilizada

                                {

                                    siglas.Add(sigla, c); //Adiciona no dicionário

                                    sucesso = true; //Marca a flag como sucesso pra sair de todos os outros for

                                }

                            }

                        }

​

                    }

                }

​

​

                if (sucesso) //Se foi possível gerar a sigla

                {

                    Console.WriteLine("Sigla " + sigla + " gerada para a cidade " + c);

                }

                else //Se nenhuma combinação foi possível

                {

                    Console.WriteLine("Não foi gerada sigla para a cidade " + c);

                }

​

​

            }

            Console.WriteLine("Siglas geradas: " + siglas.Count + " de um total de " + cidades.Count+" cidades");

​

    }

}