디닉은 네제곱입니까?

항상 최대 유량 문제를 에드몬즈-카프 알고리즘으로 푸는 지구이는 어느 날 정점 $500$개와 간선 $100000$개의 유량 문제를 보게 되었다. 지구이는 유량 그래프를 구성하고 약 $2000$바이트를 코딩한 뒤 제출했지만, 보기만 해도 기분이 좋은 초록색 글씨 "맞았습니다!!"는 볼 수 없었다. 코드 최적화를 하다가 지친 지구이는 최악의 경우 시간복잡도가 $O(V^2 E)$인 디닉 알고리즘을 찾아냈다.

디닉 알고리즘은 생각보다 간단했다.

1. 잔여 용량이 남은 간선을 길이 $1$인 간선으로 보고, 소스에서 모든 정점까지의 최단거리 $d_v$를 구한다.
2. DFS로 증가 경로를 찾아 유량을 보낸다. 이때 간선 $u \rightarrow v$는 $d_u + 1 = d_v$인 경우에만 사용한다.
3. 더 이상 유량을 보낼 수 없을 때까지 1과 2를 반복한다.

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

1. 1단계와 2단계는 최대 $O(V)$번 반복된다.
   • 이유: 매번 싱크까지의 거리 $d_{N}$이 적어도 $1$씩 증가한다. 또한 $d_{N}$은 $V$를 초과할 수 없다.
2. 1단계는 $O(E)$이다.
   • 이유: BFS로 계산할 수 있다.
3. 2단계는 $O(VE)$이다.
   • 이유: 유량을 한 번 보낼 때마다 적어도 한 간선의 잔여 용량이 가득 차므로, 증가 경로는 최대 $O(E)$번 만들어진다. 또한 증가 경로의 길이는 최대 $V$이다.

하지만 아직도 문제가 있었다. 지구이는 열심히 구현했음에도 초록색 글씨를 보지 못했다. 결국 지구이는 디닉과 함께 그 문제를 포기했다.

며칠 후, 우연히 지구이의 디닉을 보게 된 도토리는 코드에 사소한 실수가 있었고, 그 실수 때문에 쓸모없는 연산이 많아져 시간이 오래 걸렸다는 것을 알려 주었다. 지구이는 기쁜 마음에 코드를 고쳤고, 결국 아름다운 초록색 글씨를 볼 수 있었다.

하지만 지구이는 이상한 점을 느꼈다. 간선 개수가 최대 $V^2$개이므로 디닉은 $O(V^4)$이고, 정점이 $500$개면 시간 초과가 나야 정상이다. 하지만 지구이는 도저히 오래 걸리는 데이터를 만들 수 없었다.

원래는 디닉이 느리게 동작하도록 하는 임의의 유량 그래프를 출력하면 된다. 답을 하나로 정하기 위해, 아래의 유일한 그래프를 출력한다.

정점은 $4$개이고 간선은 $5$개이다. $1$번 정점에서 $4$번 정점까지 유량을 보낸다. 간선은 다음 순서와 용량으로 출력한다.

• $1 \rightarrow 2$, 용량 $3$
• $1 \rightarrow 3$, 용량 $4$
• $1 \rightarrow 4$, 용량 $5$
• $2 \rightarrow 4$, 용량 $2$
• $3 \rightarrow 4$, 용량 $2$

입력은 없다. 표준 입력이 주어지더라도 무시한다.

첫 줄에 정점 개수 $N$과 간선 개수 $M$을 공백으로 구분해 출력한다.

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

출력은 $N = 4$, $M = 5$이고, 간선은 문제에서 정한 순서와 용량을 그대로 따른 한 가지여야 한다.