잘못 구현한 디닉

항상 플로우 문제를 Edmond-Karp 알고리즘으로 푸는 지구이는 어느 날 정점 500개와 간선 100000개의 플로우 문제를 보게 되었다. 지구이는 열심히 플로우 그래프를 구성하고, 약 2000바이트를 코딩한 후 제출했지만 정답 판정을 받지 못했다. 코드 최적화를 하다가 지친 지구이는 시간복잡도가 최악의 경우 $O(V^2 E)$인 Dinic이라는 알고리즘을 찾아냈다.

Dinic 알고리즘은 다음과 같다.

1. 유량이 남은 간선을 길이 1짜리 간선으로 생각하고 소스에서 모든 정점까지의 최단거리 $d_v$를 구한다.
2. DFS로 확장 경로를 구해 플로우를 흘린다. 이때 간선 $u \to v$가 $d_u + 1 = d_v$인 경우에만 플로우를 흘린다.
3. 플로우가 없을 때까지 1과 2를 반복한다.

Dinic의 시간복잡도는 $O(V^2 E)$이며, 증명은 다음과 같다.

1. 1단계와 2단계는 최대 $O(V)$번 반복된다. 1단계와 2단계를 수행할 때마다 $d_{\mathrm{sink}}$가 최소 1씩 증가하고, $d_{\mathrm{sink}}$는 $V$를 초과할 수 없다.
2. 1단계는 $O(E)$이다. BFS로 계산할 수 있다.
3. 2단계는 $O(VE)$이다. 한 번 플로우를 흘릴 때마다 최소 한 개의 간선의 유량이 꽉 차기 때문에 확장 경로는 최대 $O(E)$번 만들어진다. 또한 확장 경로의 길이는 최대 $V$이다.

지구이는 열심히 구현했음에도 여전히 정답 판정을 받지 못했다. 도토리는 지구이의 코드를 보고, 확장 경로를 찾을 때 플로우를 흘릴 수 없는 간선들을 매번 처음부터 다시 탐색하는 실수가 있다고 알려 주었다. 지구이는 작은 예제 그래프를 보기 전까지 그 말을 믿지 않는다.

도토리를 도와 그 예제 그래프를 출력하자. 출력할 그래프는 하나뿐이다.

지구이가 푸는 문제는 1번 정점에서 $N$번 정점까지 플로우를 흘리는 문제이다. 간선은 연결 리스트로 저장하며, 리스트의 앞부분에 새 간선을 넣기 때문에 나중에 입력된 간선을 먼저 사용한다.

입력은 없다.

첫 번째 줄에 정점 개수 $N$과 간선 개수 $M$을 출력한다. $N$은 $4$이고 $M$은 $5$이다.

그다음 $M$개의 줄에 시작 정점 $s$, 끝 정점 $e$, 최대 유량 $f$를 공백으로 구분해 한 줄에 하나씩, 아래 순서대로 출력한다.

• $1$에서 $2$로 가는 용량 $3$
• $1$에서 $3$으로 가는 용량 $4$
• $1$에서 $4$로 가는 용량 $5$
• $2$에서 $4$로 가는 용량 $2$
• $3$에서 $4$로 가는 용량 $2$

그래프에 중복 간선은 없다. 각 줄은 $s$, $e$, $f$ 순서로 정수를 출력한다.