В стране \(N\) есть \(n\) городов, соединённых \(m\) односторонними дорогами. Эта, казалось бы непримечательная страна, всё же интересна двумя своими особенностями. Во-первых, неделя здесь длится \(d\) дней. Во-вторых, в каждом городе страны \(N\) расположен ровно один музей.
Турфирма «Открытые музеи» разрабатывает новую программу для путешественников, интересующихся музеями. Работникам турфирмы известно, в какие дни недели каждый из музеев открыт для посещения. Путешествие должно начаться в столице — городе с номером \(1\), причём день начала путешествия должен быть первым днём недели. Днём турист будет находиться в городе и смотреть экспозицию музея (в случае если музей, конечно, работает сегодня), а в конце дня путешествие либо заканчивается, либо турист отправляется в другой город, соединённый с текущим дорогой. Дорожная система \(N\) устроена так, что перемещение по одной дороге всегда занимает одну ночь, кроме того все дороги в стране односторонние. Во время путешествия разрешается посещать один город несколько раз.
Вам требуется разработать такой маршрут для путешествия, что количество различных музеев, которые можно посетить за его время, было бы как можно больше.
Выходные данные
Выведите одно целое число — максимальное количество различных музеев, которые можно посетить, начав путешествие в первом городе в первый день недели.
Примечание
Пояснение к первому примеру 
Максимально возможное количество музеев для посещения равно \(3\). Можно посетить \(3\) различных музея, например, так, как описано ниже.
- День 1. Сейчас день недели \(1\), и турист находится в городе \(1\). Музей там закрыт. Ночью турист направляется в город \(2\).
- День 2. Сейчас день недели \(2\), и турист находится в городе \(2\). Музей там открыт, турист его посещает. Ночью турист направляется в город \(4\).
- День 3. Сейчас день недели \(3\), и турист находится в городе \(4\). Музей там открыт, турист его посещает. Ночью турист направляется в город \(1\).
- День 4. Сейчас день недели \(1\), и турист находится в городе \(1\). Музей там закрыт. Ночью турист направляется в город \(2\).
- День 5. Сейчас день недели \(2\), и турист находится в городе \(2\). Музей там открыт, но турист в нём уже был. Ночью турист направляется в город \(3\).
- День 6. Сейчас день недели \(3\), и турист находится в городе \(3\). Музей там открыт, турист его посещает. На этом путешествие заканчивается.
Пояснение ко второму примеру 
Максимально возможное количество музеев для посещения равно \(2\). Можно посетить \(2\) различных музея, например, так, как описано ниже.
- День 1. Сейчас день недели \(1\), и турист находится в городе \(1\). Музей там открыт, турист его посещает. Ночью направляемся в город \(2\).
- День 2. Сейчас день недели \(2\), и турист находится в городе \(2\). Музей там закрыт. Ночью направляемся в город \(3\).
- День 3. Сейчас день недели \(3\), и турист находится в городе \(3\). Музей там открыт, турист его посещает. На этом путешествие заканчивается.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 3
3 1
1 2
2 4
4 1
2 3
011
110
111
001
|
3
|
|
2
|
3 3 7
1 2
1 3
2 3
1111111
0000000
0111111
|
2
|