한별이와 은하는 스트링 아트 기법으로 그림을 그려 판매하고 있다. 스트링 아트 그림은 특수한 보드 위에 못을 n개 박고, m가닥의 실로 못을 연결하는 방식으로 그릴 수 있다. 그림을 그릴 때는 완성도를 높이기 위해 어떤 못에서 다른 어떤 못으로든 실을 한 번 이상 따라가서 도달할 수 있도록 한다[역자 주: 스트링 아트 그림은 연결 그래프임].
한별이와 은하는 팬들이 스트링 아트를 직접 체험해볼 수 있도록 스트링 아트 키트를 만들어 판매하려고 했지만, 못 n개, 실 m가닥을 그냥 판매하면 도안이 있더라도 팬들이 직접 따라 그리기는 어렵다는 것을 깨달았다. 그 대신 은하가 생각한 대안은 그림의 틀을 미리 잡아서 판매하는 것이다.
스트링 아트의 틀은 여러 개의 비즈와 비즈를 서로 연결하는 m가닥의 실로 이루어지고, 모든 비즈의 쌍에 대해 두 비즈를 연결하는 경로가 정확히 하나 존재하도록 구성한다[역자 주: 스트링 아트 틀은 트리임]. 각각의 비즈에는 색이 칠해져 있고, 각각의 색의 비즈를 한 점으로 모으고 못으로 고정하면 원작자가 의도한 그림을 완성할 수 있다.
한별이와 은하는 방금 일생의 역작을 완성했다. 스트링 아트 그림을 입력받아 그림을 만들 수 있는 틀을 설계하는 프로그램을 작성하여라.
입력
첫째 줄에 그림에 있는 못의 수 n과 실의 수 m이 주어진다. (1 ≤ n ≤ 105, 1 ≤ m ≤ 2·105)
둘째 줄부터 m줄에 걸쳐 실의 정보가 uv의 꼴로 주어지며, u번째 못과 v번째 못이 실로 연결되어 있다는 의미이다. 같은 못의 쌍이 여러 번 연결되거나 못이 자기 자신과 연결되는 경우는 없다. 모든 못은 실을 통해 연결되어 있다.
출력
그림의 틀의 정보를 다음과 같이 출력한다.
첫째 줄에는 틀을 구성하는 비즈의 개수 c를 출력한다.
둘째 줄에는 각 비즈의 색 a1, a2, ..., ac (1 ≤ ai ≤ n)를 공백으로 구분하여 출력한다. k번째 색으로 칠해진 비즈는 원본 그림의 k번째 못에 대응한다.
셋째 줄부터 m줄에 걸쳐 실의 정보를 uv의 꼴로 출력한다. 이는 u번째 비즈와 v번째 비즈가 실로 연결되어 있다는 의미이다. 각 비즈의 쌍을 연결하는 경로는 정확히 하나여야 한다.
dlaud5379 1년 전
문제
한별이와 은하는 스트링 아트 기법으로 그림을 그려 판매하고 있다. 스트링 아트 그림은 특수한 보드 위에 못을 n개 박고, m가닥의 실로 못을 연결하는 방식으로 그릴 수 있다. 그림을 그릴 때는 완성도를 높이기 위해 어떤 못에서 다른 어떤 못으로든 실을 한 번 이상 따라가서 도달할 수 있도록 한다[역자 주: 스트링 아트 그림은 연결 그래프임].
한별이와 은하는 팬들이 스트링 아트를 직접 체험해볼 수 있도록 스트링 아트 키트를 만들어 판매하려고 했지만, 못 n개, 실 m가닥을 그냥 판매하면 도안이 있더라도 팬들이 직접 따라 그리기는 어렵다는 것을 깨달았다. 그 대신 은하가 생각한 대안은 그림의 틀을 미리 잡아서 판매하는 것이다.
스트링 아트의 틀은 여러 개의 비즈와 비즈를 서로 연결하는 m가닥의 실로 이루어지고, 모든 비즈의 쌍에 대해 두 비즈를 연결하는 경로가 정확히 하나 존재하도록 구성한다[역자 주: 스트링 아트 틀은 트리임]. 각각의 비즈에는 색이 칠해져 있고, 각각의 색의 비즈를 한 점으로 모으고 못으로 고정하면 원작자가 의도한 그림을 완성할 수 있다.
한별이와 은하는 방금 일생의 역작을 완성했다. 스트링 아트 그림을 입력받아 그림을 만들 수 있는 틀을 설계하는 프로그램을 작성하여라.
입력
첫째 줄에 그림에 있는 못의 수 n과 실의 수 m이 주어진다. (1 ≤ n ≤ 105, 1 ≤ m ≤ 2·105)
둘째 줄부터 m줄에 걸쳐 실의 정보가 u v의 꼴로 주어지며, u번째 못과 v번째 못이 실로 연결되어 있다는 의미이다. 같은 못의 쌍이 여러 번 연결되거나 못이 자기 자신과 연결되는 경우는 없다. 모든 못은 실을 통해 연결되어 있다.
출력
그림의 틀의 정보를 다음과 같이 출력한다.
첫째 줄에는 틀을 구성하는 비즈의 개수 c를 출력한다.
둘째 줄에는 각 비즈의 색 a1, a2, ..., ac (1 ≤ ai ≤ n)를 공백으로 구분하여 출력한다. k번째 색으로 칠해진 비즈는 원본 그림의 k번째 못에 대응한다.
셋째 줄부터 m줄에 걸쳐 실의 정보를 u v의 꼴로 출력한다. 이는 u번째 비즈와 v번째 비즈가 실로 연결되어 있다는 의미이다. 각 비즈의 쌍을 연결하는 경로는 정확히 하나여야 한다.
주어진 그림을 만들 수 있는 틀이 여러 개일 경우, 아무거나 출력한다.