Remote Training on Programming

В некоторой стране имеется N городов, соединенных сетью из M двунаправленных дорог. Между любыми двумя городами проложено не более одной дороги. Путешественник желает совершить несколько поездок из города 1 в город N таким образом, чтобы каждый раз он мог проехать по новому пути (пути считаются различными, если различны последовательности номеров дорог, по которым проходят эти пути). При этом может оказаться, что в каждой такой поездке путешественник обязательно проедет через города из некоторого множества S (города 1 и N в множество S не входят). Определите мощность множества S.