34245번 - Many edges, many paths 스페셜 저지

문제

$N$개의 정점과 $M$개 이상의 간선을 갖고 다음의 조건을 모두 충족하는 방향 그래프를 아무거나 하나 찾아 출력하시오.

• 이 그래프의 정점들은 1ドル$번부터 $N$번까지 번호가 매겨져 있다.
• 이 그래프의 모든 간선은 작은 번호에서 큰 번호로 연결된다.
• 모든 1ドル \le i < j \le n$에 대해, $i$번 정점에서 $j$번 정점으로 가는 간선은 최대 1ドル$개이다.
• 이 그래프의 모든 간선은 1ドル$번 정점에서 시작하여 $N$번 정점에서 끝나는 $k$개의 경로들 중 하나에 포함된다.
• 이 $k$개의 경로들 중 어느 것도 간선을 공유하지 않는다.

입력

첫째 줄에 $N,ドル $M$이 공백으로 구분되어 주어진다. ($N=10,円 000,ドル $M=600,円 000$)

출력

첫째 줄에 경로의 개수 $k$를 출력한다.

둘째 줄부터 $k$줄에 걸쳐 각각의 경로에 포함되는 정점의 개수와 그 정점들의 번호를 순서대로 공백으로 구분하여 출력한다.

제한

힌트