그래프를 공간에 임베딩한다는 것은 각 정점을 공간의 서로 다른 점에 놓고 각 간선을 두 정점을 잇는 단순한 호로 그려, 두 호가 공통 정점 이외에서는 만나지 않게 하는 것이다. 이 문제에서는 특정 조건을 만족하는 3차원 공간의 임베딩을 다룬다.
정점 $n$개와 간선 $m$개인 단순 무방향 그래프가 주어진다. 즉 두 정점 사이에는 간선이 최대 하나이고, 각 간선은 서로 다른 정점을 잇는다. 정점에는 $1$부터 $n$까지, 간선에는 $1$부터 $m$까지 번호가 있다. 간선 $j$는 서로 다른 두 정점 $v_j$, $w_j$를 잇는다. 각 정점에 연결된 간선은 최대 5개이다.
다음 조건을 모두 만족하는 그래프의 임베딩을 찾아라.
각 정점 $i$를 공간의 점 $(x_i,y_i,0)$에 배치한다. 좌표 $x_i$, $y_i$는 $0$ 이상 $400$ 이하의 정수여야 한다. 모든 점의 좌표는 서로 달라야 한다.
각 간선 $j$를 정점 $v_j$, $w_j$에 대응하는 점들을 양 끝점으로 하는 꺾은선(이어진 선분들의 연결)으로 배치한다. 각 선분은 $x$축, $y$축 또는 $z$축과 평행해야 한다. 꺾은선의 각 꼭짓점은 모든 좌표가 $0$ 이상 $400$ 이하인 정수여야 한다. 각 꺾은선은 양 끝점을 포함해 최대 $30$개의 꼭짓점을 가져야 한다.
꺾은선은 자기 자신과 교차하면 안 된다. 서로 다른 꺾은선은 같은 정점에 연결된 간선들을 나타내는 경우를 제외하고 어떤 점도 공유하면 안 된다. 그 경우에는 그 하나의 끝점만 공유할 수 있다.
입력
입력의 첫 번째 줄에는 두 정수 $n$, $m$이 주어진다($2\le n\le1600$, $1\le m\le4000$). 다음 $m$개 줄 중 $j$번째 줄에는 두 정수 $v_j$, $w_j$가 주어진다($1\le v_j<w_j\le n$).
각 정점에 연결된 간선은 최대 5개임이 보장된다. 또한 평행 간선은 없다. 즉 $j\ne j^{\prime}$이면 $(v_j,w_j)\ne(v_{j^{\prime}},w_{j^{\prime}})$이다.
출력
먼저 $n$개 줄을 출력한다. 그중 $i$번째 줄에는 정점 $i$를 배치한 좌표인 두 정수 $x_i$, $y_i$를 출력한다. 다음으로 $m$개 줄을 출력하며, $j$번째 줄은 간선 $j$에 대응하는 꺾은선을 다음 형식으로 나타낸다.
$$k\ x^{\prime}_1\ y^{\prime}_1\ z^{\prime}_1\ \cdots\ x^{\prime}_k\ y^{\prime}_k\ z^{\prime}_k$$
여기서 $k$는 꼭짓점 수이며 $2$ 이상 $30$ 이하이어야 한다. 점 $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1),\ldots,(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$는 꺾은선의 꼭짓점들이다. 첫 점 $(x^{\prime}_1,y^{\prime}_1,z^{\prime}_1)$은 $(x_{v_j},y_{v_j},0)$이어야 하고, 마지막 점 $(x^{\prime}_k,y^{\prime}_k,z^{\prime}_k)$는 $(x_{w_j},y_{w_j},0)$이어야 한다. 연속한 두 점을 선분으로 이어 꺾은선을 만든다. 각 선분의 길이는 양수여야 한다. 연속한 두 선분이 같은 방향이어도 된다. 예를 들어 둘 다 $x$축과 평행해도 된다.
출력한 임베딩은 위에서 언급한 모든 조건을 만족해야 한다.
주어진 입력 제한에서는 올바른 출력이 적어도 하나 존재함을 보일 수 있다. 여러 출력이 가능하면 어느 것을 출력해도 정답으로 인정된다.
참고
특수 채점에 대한 참고:
로컬 테스트를 위한 명령줄 도구가 제공된다. DOMjudge에서 파일을 다운로드할 수 있다. 도구의 맨 위에 사용법을 설명하는 주석이 있다.
예제
입력 1
3 3 1 2 1 3 2 3
출력 1
0 0 400 0 0 399 3 0 0 0 100 0 0 400 0 0 4 0 0 0 0 0 200 0 399 200 0 399 0 3 400 0 0 400 399 0 0 399 0
참고
예제 입출력 1에 대한 설명
그림 B.1은 예제 출력이 나타내는 임베딩을 보여 준다.
그림 B.1: 임베딩의 도해.