선인장 생성기

선인장은 모든 간선이 단순 사이클에 최대 하나만 속하는 연결 무향 그래프다. 사이클을 조금 허용한 트리라고 보면 된다.

정점이 수천 개인 선인장 테스트 데이터를 손으로 적기는 번거롭다. 그래서 큰 선인장을 짧은 문자열로 적는 언어 SCGL(Simple Cactus Generator Language)을 쓴다. SCGL 정의를 해석해서 그 정의가 나타내는 선인장을 출력하라.

SCGL 정의는 아래 EBNF 문법의 graph 비단말이다.

   graph = "c"
         | "c(" list ")"
         | "loop(" list ")"
         | "t(" list ")"
    list = graph { "," graph }
         | ( number | range | variable ) [ "," graph ]
  number = nzdig { "0" | nzdig }
   nzdig = "1" | "2" | ... | "8" | "9"
   range = "range(" variable "," numvar "," numvar ")"
variable = "A" | "B" | ... | "Y" | "Z"
  numvar = number | variable

graph 하나는 첫 정점과 마지막 정점이 정해진 그래프를 나타낸다.

• c는 정점이 두 개이고 그 둘을 잇는 간선이 하나인 그래프다. 한쪽이 첫 정점, 다른 한쪽이 마지막 정점이다.
• $\mathtt{c}(\sigma)$는 리스트 $\sigma$의 그래프를 왼쪽에서 오른쪽으로 사슬처럼 잇는다. 첫 번째 그래프의 마지막 정점과 두 번째 그래프의 첫 정점을 합치고, 두 번째 그래프의 마지막 정점과 세 번째 그래프의 첫 정점을 합치는 식이다. 결과의 첫 정점은 $\sigma$의 첫 그래프의 첫 정점이고, 결과의 마지막 정점은 $\sigma$의 마지막 그래프의 마지막 정점이다.
• $\mathtt{loop}(\sigma)$는 $\mathtt{c}(\sigma)$와 똑같이 사슬로 이은 다음, 마지막 그래프의 마지막 정점과 첫 그래프의 첫 정점까지 합친다. 결과의 첫 정점과 마지막 정점은 $\sigma$의 첫 그래프의 첫 정점과 마지막 정점이다. loop 규칙은 그래프가 두 개 이상인 리스트에만 쓸 수 있다.
• $\mathtt{t}(\sigma)$는 $\sigma$에 있는 모든 그래프의 첫 정점을 하나로 합친다. 결과의 첫 정점과 마지막 정점은 $\sigma$의 첫 그래프의 첫 정점과 마지막 정점이다.

리스트는 그래프를 쉼표로 나열해 적거나 반복으로 적는다. 반복은 수, range, 변수 중 하나이고, 뒤에 쉼표와 그래프 하나를 붙일 수 있다. 그래프를 붙이지 않은 반복은 c를 반복한다.

수로 적은 반복은 주어진 그래프를 그 수만큼 복사한 리스트를 나타낸다. 변수로 적은 반복은 그 변수의 현재 값만큼 복사한 리스트를 나타낸다.

$\mathtt{range}(\nu, \alpha, \beta)$로 적은 반복에는 변수 $\nu$와 수 $\alpha$, $\beta$가 있다. $\xi$가 그래프라면 $\mathtt{c}(\mathtt{range}(\nu, \alpha, \beta), \xi)$, $\mathtt{loop}(\mathtt{range}(\nu, \alpha, \beta), \xi)$, $\mathtt{t}(\mathtt{range}(\nu, \alpha, \beta), \xi)$를 range 규칙이라 부르고, $\nu$는 $\xi$ 안에서 이 규칙에 묶인 변수가 된다. range 규칙은 $\xi$를 정확히 $|\beta - \alpha| + 1$번 반복한다. $\alpha$와 $\beta$ 사이의 연속한 정수를 양 끝을 포함해 오름차순으로 늘어놓고, $\xi$의 $i$번째 복사본에서는 $\xi$에 나오는 $\nu$를 모두 그 목록의 $i$번째 정수로 바꾼다. 이렇게 만든 $|\beta - \alpha| + 1$개의 그래프가 리스트를 이루고, 이 리스트를 반복을 감싼 규칙대로 잇는다. $\alpha$와 $\beta$ 자리에는 바깥 range 규칙에 묶인 변수가 올 수도 있다.

올바른 정의에서 A부터 Z까지의 글자는 range의 $\nu$ 자리에 최대 한 번 나오고, 그 밖의 자리에 나오는 글자는 모두 묶여 있다.

$\xi$가 그래프면 $\xi$, $\mathtt{c}(\xi)$, $\mathtt{c}(1, \xi)$, $\mathtt{t}(\xi)$, $\mathtt{t}(1, \xi)$는 모두 같은 그래프를 나타낸다. $\mathtt{loop}(\xi)$와 $\mathtt{loop}(1, \xi)$는 쓸 수 없다.

한 줄에 SCGL로 적은 올바른 선인장 정의가 주어진다. SCGL의 문법과 의미만으로는 결과가 선인장이 된다고 보장되지 않지만, 입력으로 주어지는 정의는 항상 선인장을 나타낸다. 즉 모든 간선은 단순 사이클에 최대 하나만 속하고, 두 정점을 잇는 간선이 둘 이상인 경우는 없다. 예를 들어 loop(3,loop(3))이나 loop(2)는 입력에 나오지 않는다.

줄의 길이는 1000자 이하이고, 정의가 나타내는 선인장의 정점은 50000개 이하다. number로 적은 정수는 모두 50000 이하다.

정점 번호는 그래프를 만드는 과정으로 정해지므로 정답은 하나뿐이다. 먼저 모든 반복을 복사본으로 펼치고, 펼친 정의를 왼쪽에서 오른쪽으로 읽는다. 간선이 하나인 그래프 c가 나올 때마다 그 그래프의 첫 정점을 만들고 이어서 마지막 정점을 만들며, 정점은 만들어진 순서대로 1, 2, 3, ... 번을 받는다. 여러 정점이 하나로 합쳐지면 합쳐진 정점은 그중 가장 작은 번호를 쓴다. 합치기를 모두 끝낸 뒤에는 남은 정점의 순서를 유지하면서 1번부터 $n$번까지 번호를 다시 매긴다. 이렇게 하면 1번 정점이 전체 그래프의 첫 정점이 된다.

첫 줄에 정수 $n$, $m$, $p$를 출력한다. $n$은 정점의 개수, $m$은 간선의 개수, $p$는 모든 간선을 정확히 한 번씩 지나도록 그래프를 덮는 데 필요한 경로의 최소 개수다. 경로 하나는 같은 정점을 여러 번 지나도 되지만 같은 간선을 두 번 지나지는 않는다.

다음 $m$개의 줄에 간선을 하나씩 출력한다. 각 줄에는 그 간선의 두 끝 정점 $u$와 $v$를 $u < v$가 되도록 출력한다. 줄은 $u$가 작은 것부터, $u$가 같으면 $v$가 작은 것부터 정렬해서 출력한다.