마법의 숲 timer 5s memory 512MB

준혁이는 엘프들이 사는 마법의 숲을 여행하려 한다.

마법의 숲은 n개의 휴식 포인트와 m개의 양방향 오솔길로 이루어져 있는 그래프 형태이다. 

휴식 포인트는 1, 2, ... ,  n의 번호를 가지고 있으며, 오솔길은 1, 2, ... , m의 번호를 가지고 있다.

준혁이는 1번 정점에서 출발하여 n번 정점에 도달하여야 한다.

숲의 오솔길에는 많은 고블린이 서식한다.

고블린은 하이 고블린과 로우 고블린의 두 가지 종류가 있다. 

준혁이는 고블린과 싸울 수 없기 때문에, 여행을 출발하기 전에 자신을 지켜줄 엘프를 고용하여야 한다.

엘프 또한 두 가지의 종류가 있는데, 하이 엘프는 하이 고블린만을 처치할 수 있으며, 로우 엘프는 로우 고블린만을 처치할 수 있다. 

또한, 한 명의 엘프는 하나의 길에서 한 마리의 고블린만을 처치할 수 있다.

예를 들어, 하이 고블린이 2마리, 로우 고블린이 3마리가 서식하는 길을 지나려면 하이 엘프를 2명 이상, 로우 엘프를 3명 이상 고용하였어야 한다.

엘프를 고용하는 것은 큰 비용이 들기 때문에, 준혁이는 자신이 고용해야 하는 엘프의 총 인원의 최솟값을 구하고 싶다. 

고용하는 엘프의 총 인원은 고용하는 하이 엘프와 로우 엘프의 수의 합이다.

여러분이 불쌍한 준혁이를 도와 고용해야 하는 엘프의 총 인원의 최솟값을 대신 구해주자!​