선인장 그래프 만들기

문제

선인장은 모든 간선이 많아야 하나의 단순 사이클에만 놓이는 연결 무향 그래프다. 선인장에는 루프도 다중 간선도 없다. 사이클을 얼마간 허용한 트리라고 보면 된다.

다음 방식으로 그래프를 조립한다. 먼저 색의 개수 $\hat{c}$ 를 정한다. 모든 정점에는 $1$ 이상 $\hat{c}$ 이하의 정수로 나타내는 색이 하나씩 붙는다. 작업 공간은 정점이 하나씩 들어 있는 그래프 $n$ 개로 시작한다. $i$ 번째 그래프에는 정점 $i$ 하나만 있고, 색은 $1$ 이며 간선은 없다.

다음 세 가지 연산을 쓸 수 있다.

join $a$ $b$ : 정점 $a$ 가 있는 그래프와 정점 $b$ 가 있는 그래프를 하나로 합친다. 간선은 만들지 않는다. 정점 $a$ 와 $b$ 는 서로 다른 그래프에 있어야 한다.
recolor $a$ $c_1$ $c_2$ : 정점 $a$ 가 있는 그래프에서 색이 $c_1$ 인 정점을 모두 색 $c_2$ 로 바꾼다.
connect $a$ $c_1$ $c_2$ : 정점 $a$ 가 있는 그래프에서 색이 $c_1$ 인 정점과 색이 $c_2$ 인 정점의 모든 쌍 사이에 간선을 만든다. $c_1 = c_2$ 이면 루프는 만들지 않는다. 이미 있는 간선을 또 만들면 평행한 두 번째 간선이 생긴다. 이 문제에서 다중 간선은 허용하지 않으므로 그런 경우가 생기면 안 된다.

마지막 연산까지 적용하면 작업 공간에는 그래프가 하나만 남고, 그 시점의 정점 색은 상관없다.

어떤 그래프를 이 방식으로 조립할 수 있는 가장 작은 $\hat{c}$ 를 그 그래프의 클리크 너비라고 한다. 클리크 너비가 유계인 그래프에서는 조립 과정을 따라가는 동적 계획법으로 NP-난해 문제 상당수를 다항 시간에 푼다. 일반 그래프의 클리크 너비를 정확히 구하는 문제는 NP-난해이지만, 몇몇 그래프 부류에서는 상한이 알려져 있다. 선인장의 클리크 너비는 $4$ 이하다.

선인장이 주어진다. 출력 절에서 정한 구성 방법을 그대로 따라 $\hat{c} = 4$ 로 조립하라.

입력

첫 줄에 정점 수 $n$ 과 경로 수 $m$ 이 주어진다 ( $1 \le n \le 50000$ , $0 \le m \le 50000$ ). 정점 번호는 $1$ 부터 $n$ 까지다. 그래프의 간선은 서로 겹치지 않는 경로 $m$ 개로 주어진다.

다음 $m$ 개 줄에는 경로가 한 줄에 하나씩 주어진다. 각 줄은 정수 $k_i$ ( $2 \le k_i \le 1000$ )로 시작하고, 이어서 $1$ 이상 $n$ 이하인 정점 번호가 $k_i$ 개 온다. 한 줄에서 이웃한 두 정점 번호는 서로 다르다. 같은 정점을 여러 번 지나는 경로도 주어질 수 있지만, 그래프의 모든 간선은 입력 전체에서 정확히 한 번씩만 나온다.

이렇게 주어지는 그래프는 선인장이다.

출력

같은 선인장을 조립하는 연산 순서는 여러 가지이므로, 이 문제는 그중 하나를 지정한다.

선인장을 정점 $1$ 을 루트로 잡는다. 선인장의 모든 간선은 정확히 하나의 블록에 속한다. 블록은 단순 사이클이거나, 어떤 사이클에도 놓이지 않는 간선인 다리다. 서로 다른 두 블록이 공유하는 정점은 많아야 하나다. 블록 $B$ 에서 정점 $1$ 에 가장 가까운 정점을 $\mathrm{top}(B)$ 라고 하면 그 정점은 유일하다. $\mathrm{top}(B) = v$ 인 블록 $B$ 를 정점 $v$ 에 매달린 블록이라고 하자.

정점 $v$ 에 매달린 블록은 $v$ 를 뺀 나머지 정점 번호의 최솟값이 작은 것부터 차례로 처리한다. 한 정점에 매달린 블록끼리는 $v$ 말고 공유하는 정점이 없으므로 이 최솟값은 모두 다르고 순서가 하나로 정해진다.

정점 $v$ 에 매달린 사이클 블록 $B$ 의 정점이 $k$ 개라고 하자 ( $k \ge 3$ ). $B$ 안에서 $v$ 와 인접한 정점은 정확히 둘이다. 그중 번호가 작은 쪽을 $w_1$ 로 두고, $w_1$ 에서 $v$ 의 반대 방향으로 사이클을 따라가면 $w_1, w_2, \ldots, w_{k-1}$ 을 얻는다. $w_{k-1}$ 은 $v$ 와 인접한 나머지 한 정점이다.

아래 재귀 절차를 정의한다. 유사 코드의 <x>는 정점 $x$ 의 번호로 바꿔 쓰고, emit 하는 문자열은 각각 출력 한 줄이다.

build(v):
    for each block B hanging from v, in the order defined above:
        if B is the bridge {v, u}:
            build(u)
            emit "r <u> 1 3"
            emit "j <v> <u>"
            emit "c <v> 1 3"
            emit "r <v> 3 2"
        else B is the cycle v, w[1], w[2], ..., w[k-1]:
            build(w[1])
            emit "r <w[1]> 1 3"
            build(w[2])
            emit "r <w[2]> 1 4"
            emit "j <w[1]> <w[2]>"
            emit "c <w[1]> 3 4"
            for i = 3, 4, ..., k-1:
                build(w[i])
                emit "j <w[1]> <w[i]>"
                emit "c <w[1]> 4 1"
                emit "r <w[1]> 4 2"
                emit "r <w[1]> 1 4"
            emit "j <v> <w[1]>"
            emit "c <v> 1 3"
            emit "c <v> 1 4"
            emit "r <v> 3 2"
            emit "r <v> 4 2"

build(1)을 실행해 나온 줄을 순서대로 모은다. 첫 줄에 줄 수 $q$ 를 출력하고, 다음 $q$ 개 줄에 그 줄을 순서대로 출력한다. $n = 1$ 이면 아무 줄도 나오지 않으므로 $0$ 만 한 줄에 출력한다.

이 연산 순서는 언제나 입력 선인장을 정확히 조립하고, 색은 $1$ 부터 $4$ 까지만 쓰며, $q$ 는 $10^6$ 을 넘지 않는다.

노트

build(v)가 끝나면 정점 $v$ 의 색은 $1$ 이고, 같은 그래프에 있는 나머지 정점의 색은 모두 $2$ 다. 블록을 이어 붙이는 모든 시점에 색 $3$ 과 $4$ 가 비어 있고, 그래서 네 가지 색이면 충분하다.