단절점과 이중 연결 성분

정점이 $N$개이고 간선이 $M$개인 무방향 그래프가 주어진다. 정점의 번호는 $1$부터 $N$까지이다. 자기 루프는 없고 중복 간선은 있을 수 있다.

다음 세 대상을 구해 보자.

• 단절점: 삭제하면 그래프의 연결 성분 수가 증가하는 정점
• 단절선: 삭제하면 그래프의 연결 성분 수가 증가하는 간선
• 정점 이중 연결 성분: 집합에 속한 서로 다른 두 정점이 연결되어 있고, 두 정점 이외의 정점 하나를 삭제해도 서로 연결되어 있는 정점 집합 중 포함 관계로 극대인 집합

단절선의 양 끝 정점도 하나의 정점 이중 연결 성분을 이루며, 고립점은 혼자 하나의 성분을 이룬다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 100)$

각 테스트 케이스의 첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 3\,000; 0 \le M \le 200\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 양 끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \ne v)$

전체 테스트 케이스에서 $N$의 합은 $10\,000$ 이하이고 $M$의 합은 $300\,000$ 이하이다.

각 테스트 케이스마다 다음 순서로 출력한다.

• 단절점의 수와 단절점의 번호를 공백으로 구분하여 한 줄에 출력한다. 정점 번호는 오름차순으로 출력한다.
• 단절선의 수를 한 줄에 출력한다. 이어서 각 단절선의 양 끝 정점 번호를 작은 번호부터 공백으로 구분하여 한 줄에 출력한다. 간선은 양 끝 정점 번호의 순서쌍을 기준으로 사전순으로 출력한다.
• 정점 이중 연결 성분의 수를 한 줄에 출력한다. 각 성분의 정점 번호를 오름차순으로 정렬하고, 정점 목록을 사전순으로 정렬한다. 각 성분의 크기와 정점 번호를 공백으로 구분하여 한 줄에 출력한다.