Agència de viatges P91924
Una agència de viatges ven rutes. En particular, disposa d’m parells de ciutats connectades amb vols directes en ambdós sentits. Una ruta és una seqüència de ciutats tal que es pot volar directament des de cada ciutat a la següent, amb dues condicions:
- Cal fer almenys un vol.
- Les ciutats de la ruta han d’aparèixer en ordre alfabètic.
L’agència vol calcular quantes rutes pot oferir als seus clients. La podeu ajudar?
Per exemple, si tenim vols directes entre Barcelona i París, entre Barcelona i Londres, i entre París i Londres, llavors hi ha exactament quatre rutes possibles: Barcelona → París, Barcelona → Londres, Barcelona → Londres → París, i Londres → París.
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vols entre ciutats m. Segueixen els m vols amb el format que podeu veure als exemples. Els noms de ciutats estan compostos només per entre 1 i 10 lletres minúscules. No hi ha vols entre una ciutat i ella mateixa, ni vols repetits. Si anomenem n al nombre de ciutats diferents d’un cas, podeu suposar 2 ≤ n ≤ 104, i m ≤ 5n.
Sortida
Per a cada cas, escriviu el nombre de rutes possibles. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul 108 + 7.
Input
3 barcelona <-> paris paris <-> londres londres <-> barcelona 4 a <-> aa aaa <-> a b <-> c d <-> c
Output
4 5
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++