22954번 - 그래프 트리 분할 스페셜 저지

정점 $N$개, 간선 $M$개의 그래프가 주어진다.

각 정점은 $1$부터 $N$까지 번호가 매겨져 있고, 간선도 입력되는 순서대로 $1$부터 $M$까지 번호가 매겨져 있다.

그래프에서 원하는 만큼 간선을 삭제해, 서로 다른 크기의 트리 2개로 분할해보자!

각각의 트리는 하나 이상의 정점을 가지고 있어야 하며, 두 트리가 동일한 정점이나 간선을 공유해서는 안 된다.

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

두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u \ne v$)

이는 $u$번 정점과 $v$번 정점을 잇는 양방향 간선이 존재함을 나타낸다. 중복 간선은 주어지지 않는다.

그래프를 분할할 수 없다면 첫 번째 줄에 -1을 출력하고 종료한다.

분할 할 수 있는 방법이 존재한다면, 아무거나 하나, 아래와 같은 형식으로 출력한다.

첫 번째 줄에 두 트리의 크기 $N_1, N_2$을 출력한다. ($N_1$과 $N_2$는 서로 다른 양의 정수이고, $N_1 + N_2 = N$을 만족해야 한다.)

두 번째 줄에는 첫 번째 트리에 속한 정점 $N_1$개의 번호를 출력한다.

세 번째 줄에는 첫 번째 트리에 속한 간선 $N_1 - 1$개의 번호를 출력한다.

네 번째 줄에는 두 번째 트리에 속한 정점 $N_2$개의 번호를 출력한다.

다섯 번째 줄에는 두 번째 트리에 속한 간선 $N_2 - 1$개의 번호를 출력한다.

출력한 트리 각각은 연결 그래프이고, 동일한 정점이나 간선을 공유해서는 안된다.

출력하는 모든 정점의 번호는 $1$이상 $N$이하를, 간선의 번호는 $1$이상 $M$이하를 만족해야 한다.