cho.sh

선인장 생성기

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

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

정점이 수천 개인 선인장 테스트 데이터를 손으로 적기는 번거롭다. 그래서 큰 선인장을 짧은 문자열로 적는 언어 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는 정점이 두 개이고 그 둘을 잇는 간선이 하나인 그래프다. 한쪽이 첫 정점, 다른 한쪽이 마지막 정점이다.
  • c(σ)\mathtt{c}(\sigma)는 리스트 σ\sigma의 그래프를 왼쪽에서 오른쪽으로 사슬처럼 잇는다. 첫 번째 그래프의 마지막 정점과 두 번째 그래프의 첫 정점을 합치고, 두 번째 그래프의 마지막 정점과 세 번째 그래프의 첫 정점을 합치는 식이다. 결과의 첫 정점은 σ\sigma의 첫 그래프의 첫 정점이고, 결과의 마지막 정점은 σ\sigma의 마지막 그래프의 마지막 정점이다.
  • loop(σ)\mathtt{loop}(\sigma)는 c(σ)\mathtt{c}(\sigma)와 똑같이 사슬로 이은 다음, 마지막 그래프의 마지막 정점과 첫 그래프의 첫 정점까지 합친다. 결과의 첫 정점과 마지막 정점은 σ\sigma의 첫 그래프의 첫 정점과 마지막 정점이다. loop 규칙은 그래프가 두 개 이상인 리스트에만 쓸 수 있다.
  • t(σ)\mathtt{t}(\sigma)는 σ\sigma에 있는 모든 그래프의 첫 정점을 하나로 합친다. 결과의 첫 정점과 마지막 정점은 σ\sigma의 첫 그래프의 첫 정점과 마지막 정점이다.

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

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

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

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

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

입력

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

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

출력

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

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

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