SOJ ONLINE JUDGE

강한 연결 요소

난이도: Platinum V 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB
강한 연결 요소

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.

두 정점 $u$, $v$에 대해 $u$에서 $v$로 이동할 수 있고 $v$에서 $u$로도 이동할 수 있다면 두 정점은 같은 강한 연결 요소에 속한다.

주어진 그래프를 강한 연결 요소로 분해하여 출력하라.

입력

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 10\,000, 0 \leq M \leq 100\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 방향 간선을 나타내는 두 정수 $u$, $v$가 주어진다. $(1 \leq u,v \leq N, u \neq v)$

이는 $u$번 정점에서 $v$번 정점으로 향하는 간선이 있다는 뜻이다.

같은 방향 간선은 두 번 이상 주어지지 않는다.

출력

첫 번째 줄에 강한 연결 요소의 개수를 출력한다.

두 번째 줄부터 각 강한 연결 요소에 포함된 정점 번호를 오름차순으로 출력하고, 마지막에 -1을 출력한다.

예제 입력 1

8 10
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7
7 6
7 8

예제 출력 1

4
8 -1
6 7 -1
4 5 -1
1 2 3 -1

예제 입력 2

5 0

예제 출력 2

5
1 -1
2 -1
3 -1
4 -1
5 -1

제출