통신망은 \(N\) 개의 라우터와, 라우터 사이를 잇는 \(M\) 개의 단방향 광케이블로 이루어져 있다. 어떤 두 라우터 사이에는 같은 방향의 케이블이 여러 가닥 있을 수도 있다.

본사 라우터 \(S\) 에서 데이터센터 라우터 \(T\) 까지 데이터를 보내려 한다. 한 케이블은 한 번만 사용할 수 있을 때 (어떤 케이블도 두 경로에 동시에 쓰이지 않도록), 서로 간선이 겹치지 않는(edge-disjoint) \(S \to T\) 경로를 최대 몇 개까지 동시에 확보할 수 있는지 구하여라. 경로끼리 같은 라우터를 거치는 것은 허용된다. 경로가 하나도 없으면 답은 \(0\) 이다.

• \(2 \le N \le 500\)
• \(0 \le M \le 5000\)
• \(1 \le u,v \le N\), \(u \ne v\)
• \(1 \le S,T \le N\), \(S \ne T\)
• 같은 \((u,v)\) 케이블이 여러 개 있을 수 있다

첫 줄에 라우터 수 \(N\), 케이블 수 \(M\), 출발 \(S\), 도착 \(T\) 가 주어진다.

이어지는 \(M\) 개의 줄에 케이블 \(u\ v\) (방향 \(u \to v\)) 가 주어진다.

간선이 겹치지 않는 \(S \to T\) 경로의 최대 개수를 정수 한 줄로 출력한다.

riseoj 작성

출처 Original